Maximum Milk Production

Farmer John has N cows to milk. Each cow takes exactly one unit of time to be milked. However, each cow i will only produce g_i gallons of milk if she is milked before her deadline at time d_i. Time starts at t = 0, so at most x cows can be milked by time t = x.

Your task is to help Farmer John determine the maximum amount of milk he can obtain if he milks the cows optimally.

Constraints:

• \(1 \leq N \leq 10{,}000\)
• \(1 \leq g_i \leq 1000\)
• \(1 \leq d_i \leq 10{,}000\)

Hint: A greedy algorithm using a min-heap can be used to solve this scheduling problem. Process cows sorted by their deadline and use the heap to keep track of the milk values scheduled. If the number of cows scheduled exceeds the current cow's deadline, remove the cow with the smallest milk production.

inputFormat

The input begins with a single integer N indicating the number of cows. The following N lines each contain two space-separated integers: g and d, where g is the gallons of milk the cow produces if milked before her deadline, and d is the deadline by which she must be milked.

outputFormat

Output a single integer representing the maximum total amount of milk that Farmer John can collect by milking the cows optimally.

sample

3
10 3
20 2
30 1

60