Cup Ramen

Interview

Time limit2sMemory limit256 MB

Summary

Given N jobs each taking one time unit with a deadline and a reward, choose which jobs to schedule to maximize total reward earned by finishing before deadlines.

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

Problem

Sangwook, a teaching assistant, gave Dongho N problems and announced how many cups of ramen Dongho would receive for solving each one. Because Dongho was extremely confident, Sangwook also assigned a deadline to each problem.

Problem number	1	2	3	4	5	6	7
Deadline	1	1	3	3	2	2	6
Cups of ramen	6	7	2	1	4	5	1

In the situation above, if Dongho solves the problems in the order 2, 6, 3, 1, 7, 5, 4, then problems 2, 6, 3, and 7 are completed before their deadlines. He receives a total of 15 cups of ramen.

Find the maximum number of cups of ramen Dongho can receive. In the situation above, the maximum is 15.

Solving one problem takes exactly 1 unit of time. Every deadline is a positive integer not greater than N. The number of cups awarded for each problem, and the maximum total number of cups Dongho can receive, are positive integers less than 2^31.

Input

The first line contains the number of problems N (1 ≤ N ≤ 200,000).

Each of the next N lines contains two integers separated by a space: the deadline of the i-th problem and the number of cups of ramen received for solving it.

Output

Print the maximum number of cups of ramen Dongho can receive.

Examples1

Example 1
Input
```
7
1 6
1 7
3 2
3 1
2 4
2 5
6 1
```
Expected output
```
15
```