Монгол ардын үлгэр

Time limit2sMemory limit512 MB

Summary

Choose a subset whose size is at most the total weight of the remaining stones, maximizing the value of that chosen subset.

Level: Hard8 of 10
Topics: Dynamic programming, Sorting, Greedy, Array
Solved: No attempts yet

Problem

Explorer Дондог and his assistant Индиана Жонс found $N$ gemstones on their latest expedition. Each stone has value $C_i$ and weight $T_i$ . Дондог came up with an interesting way to split the treasure. He divides it so that he takes a number of stones no greater than the total weight of the stones he gives to Жонс. For example, if Жонс has 3 stones with weights 1, 2, 1, then Дондог can take up to 4 stones for himself. Help Дондог make the total value of the stones he takes as large as possible.

Input

The first line gives the number of gemstones $N$ ( $1 \le N \le 2000$ ). Each of the next $N$ lines gives a pair $T_i, C_i$ ( $1 \le T_i \le 2000$ , $1 \le C_i \le 10^9$ ), the weight and value of the $i$ -th stone.

Output

Print on one line the maximum total value of the stones Дондог can take.

Hint

In the example above, he gave the last two stones to Жонс and took a number of stones equal to the sum of the weights of those last two stones.

Examples1

Example 1
Input
```
4
2 10
1 20
1 5
1 3
```
Expected output
```
30
```