P2647 Maximum Profit

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)$.

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 a single line with the maximum profit.

### 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