描述
现在你面前有 $n$ 个物品,编号分别为 $1,2,3,\cdots,n$。你可以在这当中任意选择任意多个物品。其中第 $i$ 个物品有两个属性 $W_i$ 和 $R_i$,当你选择了第 $i$ 个物品后,你就可以获得 $W_i$ 的收益;但是,你选择该物品以后选择的所有物品的收益都会减少 $R_i$。现在请你求出,该选择哪些物品,并且该以什么样的顺序选取这些物品,才能使得自己获得的收益最大。
注意,收益的减少是会叠加的。比如,你选择了第 $i$ 个物品,那么你就会获得了 $W_i$ 的收益;然后你又选择了第 $j$ 个物品,你又获得了 $W_j-R_i$ 收益;之后你又选择了第 $k$ 个物品,你又获得了 $W_k-R_i-R_j$ 的收益;那么你获得的收益总和为 $W_i+(W_j-R_i)+(W_k-R_i-R_j)$。
输入
第一行一个正整数 $n$,表示物品的个数。
接下来第 $2$ 行到第 $n+1$ 行,每行两个正整数 $W_i$ 和 $R_i$,含义如题目所述。
输出
输出仅一行,表示最大的收益。
样例
- 复制
- 复制
- 复制
- 复制
提示
- $100\%$ 的数据满足:$n \le 10000$,$0 \le W_i,R_i \le 2\times 10^5$。

关注我们