Problem Description

On this day, Xiaoming is moving bricks.

He has a total of $n$ bricks. He finds that the weight of the $i$-th brick is $w_{i}$ and its value is $v_{i}$. He suddenly wants to choose some of these bricks and stack them from bottom to top into a tower. For each brick in the tower, the sum of the weights of all bricks above it must not exceed its own value.

He wants to know what the maximum possible total value of such a tower is (that is, the sum of the values of all bricks in the tower).

Input Format

The input has $n+1$ lines. The first line contains a positive integer $n$, which represents the number of bricks.

The next $n$ lines each contain two positive integers $w_{i}, v_{i}$, representing the weight and value of each brick.

Output Format

One line, an integer representing the answer.

5
4 4
1 1
5 2
5 5
4 3

10

Hint

Sample Explanation

Choose bricks $1$, $2$, and $4$. Stack them from top to bottom in the order $2$, $1$, $4$. The total value is $4+1+5=10$.

Constraints and Notes

For $20\%$ of the testdata, it is guaranteed that $n \leq 10$.

For $100\%$ of the testdata, it is guaranteed that $n \leq 1000$; $w_{i} \leq 20$; $v_{i} \leq 20000$.

Lanqiao Cup 2022 National Contest B Group, Problem J.

Translated by ChatGPT 5