Assignments

Interview

Time limit1sMemory limit256 MB

Summary

Given deadlines and scores for N assignments, pick a subset schedulable within their deadlines to maximize total score.

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

Problem

Ungchan has many assignments to finish. He can finish one assignment per day, and each assignment has a deadline, so he may not be able to finish all of them. Finishing an assignment earns its score, but an assignment whose deadline has passed earns nothing.

Find the maximum total score Ungchan can earn.

Input

The first line contains the number of assignments $N$ ( $1 \le N \le 1000$ ).

Each of the next $N$ lines describes one assignment with two integers $d$ ( $1 \le d \le 1000$ ) and $w$ ( $1 \le w \le 100$ ). Here $d$ is the number of days left until the deadline, so the assignment can only be finished on one of days 1 through $d$ . The value $w$ is the score earned by finishing it.

Output

Print the maximum total score on the first line.

Hint

In the first example, finishing the fifth, fourth, second, first, and seventh assignments in that order and giving up the third and sixth assignments earns 185 points.

Examples6

Example 1

Input

Expected output

Example 2
Input
```
1
1 1
```
Expected output
```
1
```
Example 3
Input
```
1
1000 100
```
Expected output
```
100
```
Example 4
Input
```
4
1 10
1 20
1 5
1 30
```
Expected output
```
30
```
Example 5
Input
```
5
5 1
5 2
5 3
5 4
5 5
```
Expected output
```
15
```
Example 6
Input
```
3
1 5
2 5
3 5
```
Expected output
```
15
```