Milk Scheduling

Interview

Time limit1sMemory limit128 MB

Summary

Schedule at most one cow per time unit before its deadline to maximize total gallons of milk.

Level: Medium5 of 10
Topics: Greedy, Heap, Sorting
Solved: No attempts yet

Problem

Farmer John has $N$ cows that need to be milked. Milking one cow takes exactly one unit of time.

The cows are impatient, so a cow refuses to be milked if Farmer John waits too long. Cow $i$ gives $g_i$ gallons of milk, but only if she is milked before her deadline at time $d_i$ . Time starts at $t = 0$ , so at most $x$ cows in total can be milked before time $x$ . In other words, a cow with deadline $d_i$ has to take one of the first $d_i$ slots.

Find the largest amount of milk Farmer John can get if he milks the cows in the best possible order.

Input

The first line contains the number of cows $N$ . ( $1 \le N \le 10000$ )

Each of the next $N$ lines contains two integers separated by a space: the gallons $g_i$ and the deadline $d_i$ of cow $i$ . ( $1 \le g_i \le 1000$ , $1 \le d_i \le 10000$ )

Output

Print the maximum number of gallons of milk Farmer John can obtain, on one line.

Examples1

Example 1
Input
```
4
10 3
7 5
8 1
2 1
```
Expected output
```
25
```