USACO 2005 November Silver, poj 3045- 서커스 > 문제은행 : 정보올림피아드&알고리즘




1549 : 서커스

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
24 회   
시도횟수
122 회   

문제

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

 

그들은 다른 묘기를 할 수 없어서 곡예를 하기로 했다.

그들이 하는 곡예는 단순히 소들을 쌓아 올리는 것이다. 소들이 차례로 아래에서 위로 올라가서 N층을 쌓는 것이다.

쌓아 올린 탑이 무너질 확률을 최소로 하도록 올라가는 순서를 정하려고 한다.

 

모든 소들은 각각 무게(1≤Wi≤10,000)와 힘(1≤Si≤1,000,000,000)이 주어진다.

특정 소가 무너질 위험은 그 소 위에 올려진 무게의 합 빼기 그 소의 힘과 같다.

 

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


입력형식

먼저 N이 입력되고 다음 N줄에 걸쳐 각 소의 무게와 힘이 주어진다.

출력형식

가장 위험한 소의 위험도의 가능한 최소값을 출력한다.

입력 예

3
10 3
2 5
3 3

출력 예

2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP