Description

You are given $n$ items, numbered $1, 2, 3, \cdots, n$. You may choose any subset of them in any order. The $i$-th item has two attributes $W_i$ and $R_i$. When you choose the $i$-th item, you immediately gain a profit of $W_i$; however, the profits of all items chosen after this item are reduced by $R_i$. Determine which items to choose and in what order to choose them so that the total profit is maximized.

Note that the reductions are cumulative. For example, if you choose item $i$, you gain $W_i$; then if you choose item $j$, you gain $W_j - R_i$; afterwards, if you choose item $k$, you gain $W_k - R_i - R_j$; hence the total profit is $W_i + (W_j - R_i) + (W_k - R_i - R_j)$.

Input Format

The first line contains a positive integer $n$, the number of items.

Lines $2$ through $n+1$ each contain two non-negative integers $W_i$ and $R_i$, as described above.

Output Format

Output a single line with the maximum profit.

2
5 2
3 5

6

Hint

Constraints

• 20% of the testdata satisfies $n \le 5$, $0 \le W_i, R_i \le 1000$.
• 50% of the testdata satisfies $n \le 15$, $0 \le W_i, R_i \le 1000$.
• 100% of the testdata satisfies $n \le 3000$, $0 \le W_i, R_i \le 2 \times 10^5$.

Sample Explanation

We can choose item $1$ to gain $5$ profit; then choose item $2$ to gain $3 - 2 = 1$ profit. The total profit is $5 + 1 = 6$.

Translated by ChatGPT 5