Maximizing Profits with Ordered Item Selections

You are given n items numbered from 1 to n. Each item i has two attributes: a profit value \(W_i\) and a penalty value \(R_i\). You can choose an arbitrary subset of these items and arrange them in any order. When you select an item i, you immediately gain a profit of \(W_i\). However, for every item chosen after item i, the profit you obtain will be reduced by \(R_i\). That is, if the items are chosen in order \(i_1, i_2, \ldots, i_k\), then the total profit is calculated as follows:

[ \text{Total Profit} = W_{i_1} + \Big(W_{i_2} - R_{i_1}\Big) + \Big(W_{i_3} - (R_{i_1}+R_{i_2})\Big) + \cdots + \Big(W_{i_k} - (R_{i_1}+R_{i_2}+\cdots+R_{i_{k-1}})\Big). ]

Your task is to choose a subset of items and determine a selection order that maximizes the total profit.

Hint: A key observation is that if you swap two items \(i\) and \(j\) such that \(R_i \le R_j\), then placing \(i\) before \(j\) results in a lower overall penalty. Thus, an optimal strategy is to sort the items in ascending order of \(R\) and then decide which items to pick. Notice that if you have already picked some items and the cumulative sum of their \(R\) values is c, then choosing a new item i will increase your profit by \(W_i - c\) if \(W_i > c\); otherwise, it is better to skip it.

inputFormat

The first line contains an integer n (the number of items). The following n lines each contain two integers \(W_i\) and \(R_i\), representing the profit and penalty of the i-th item respectively.

For example:

3
2 1
4 2
5 3

outputFormat

Output a single integer representing the maximum total profit achievable by optimally selecting and ordering a subset of items.

sample

3
2 1
4 2
5 3

7