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. 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 value of N.

Lines 2..1+N: Line i+1 contains the integers g_i and d_i.

The maximum number of gallons of milk Farmer John can obtain.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > December > Silver