P16012

最大收益

难度 6 级 小学 动态规划入门 背包DP 贪心 排序
讨论 统计 15通过 52提交 28.8%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

现在你面前有 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,含义如题目所述。

输出

输出仅一行,表示最大的收益。

样例

样例 1
输入
2
5 2
3 5
输出
6
样例 2
输入
2
5 12
3 15
输出
5

提示

  • 100\% 的数据满足:n \le 10000,0 \le W_i,R_i \le 2\times 10^5。
Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交