농부 창호의 소들 N(1≤N≤50,000)마리가 서커스에 참여할 계획이다.

그들은 다른 묘기를 할 수 없어서 곡예를 하기로 했다. 그들이 하는 곡예는 단순히 소들을 쌓아 올리는 것이다. 소들이 차례로 아래에서 위로 올라가서 N층을 쌓는 것이다. 쌓아 올린 탑이 무너질 확률을 최소로 하도록 올라가는 순서를 정하려고 한다.

모든 소들은 각각 무게(1≤Wi≤10,000)와 힘(1≤Si≤1,000,000,000)이 주어진다. 특정 소가 무너질 위험은 그 소 위에 올려진 무게의 합 빼기 그 소의 힘과 같다.

가장 위험한 소의 무너질 위험이 최소가 되도록 순서를 정하자.

서커스 timer 1s memory 64MB

서커스 1s 64MB