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

탐험가 Дондог와 그의 조수 Индиана Жонс는 이번 탐험에서 $N$개의 보석을 찾았다. 각 보석은 $C_i$의 가치와 $T_i$의 무게를 가진다. Дондог는 보석을 나누는 흥미로운 방법을 생각해냈다. 그는 Жонс에게 준 보석들의 총 무게보다 많지 않은 개수의 보석을 자신이 가져가도록 나눈다. 예를 들어 Жонс에게 무게가 1, 2, 1인 보석 3개가 있다면, Дондог는 4개까지의 보석을 자신이 가져갈 수 있다. Дондог가 가져갈 보석들의 가치 합을 최대로 만드는 방법을 도와주자.

첫째 줄에 보석의 수 $N$ ($1 \le N \le 2000$)이 주어진다. 다음 $N$개의 줄에는 $T_i, C_i$ ($1 \le T_i \le 2000$, $1 \le C_i \le 10^9$)가 주어지며, 각각 $i$번째 보석의 무게와 가치를 나타낸다.

한 줄에 Дондог가 가져갈 수 있는 보석들의 가치 합의 최댓값을 출력한다.

위의 예에서 Жонс에게 마지막 두 보석을 주고, 자신은 마지막 두 보석의 무게 합과 같은 개수의 보석을 가져갔다.