프로그램 명: usa_msched
제한시간: 1 초

농부 존의 N마리의 소들은 각기 다른 양의 우유를 생산할 수 있습니다. (1 <= N <= 10,000) 하지만 오래 기다린 젖소들은 짜증이 나게 되어 우유짜는 것을 거부합니다. 좀 더 정확히는 시간이 0부터 시작되고, i번째 소는 Di 미만에 우유를 짜면 Gi만큼의 우유를 얻을 수 있습니다. (1 <= Gi <= 1,000, 1 <= Di <= 10,000) 하지만 농장에는 농부 존 혼자만 있어서 단위 시간 동안 단 한마리의 소에게 우유를 짤 수 있습니다.

각 소들의 생산량과 만료 시간이 주어질 때, 가장 많이 생산할 수 있는 우유의 양을 구해주세요.

입력

첫 번째 줄에는 N이 주어집니다. 두 번째 줄부터 N개의 줄에 걸쳐서 우유의 양 Gi와 만료 시간 Di가 주어집니다.

출력

생산할 수 있는 우유의 최대 양을 출력하세요.

입출력 예 

입력 

4 
10 3 
7 5 
8 1 
2 1 

출력 

25

입출력 보충

농부 존은 3번째 소에게 우유를 8만큼 짭니다. 이 후 4번째 소에게 우유를 얻을 수 없습니다. 이 후 1번째 소와 2번째 소에게 우유를 짜면 25가 나오게 됩니다.
Farmer John has N cows that need to be milked (1 <= N <= 10,000), each of which takes only one unit of time to milk.

Being impatient animals, some cows will refuse to be milked if Farmer John waits too long to milk them. More specifically, cow i produces g_i gallons of milk (1 <= g_i <= 1000), but only if she is milked before a deadline at time d_i (1 <= d_i <= 10,000). Time starts at t=0, so at most x total cows can be milked prior to a deadline at time t=x.

Please help Farmer John determine the maximum amount of milk that he can obtain if he milks the cows optimally.

입력

출력

* Line 1: The maximum number of gallons of milk Farmer John can obtain.

입출력 예

입력

4
10 3
7 5
8 1
2 1

출력

25

INPUT DETAILS:

There are 4 cows.  The first produces 10 gallons of milk if milked by time
3, and so on.

OUTPUT DETAILS:

Farmer John milks cow 3 first, giving up on cow 4 since she cannot be
milked by her deadline due to the conflict with cow 3.  Farmer John then
milks cows 1 and 2.

출처:usaco/2013/dec/silver
번역:Fate
[질/답] [제출 현황] [푼 후(0)]
[ 채 점 ] [홈으로]  [뒤 로]