分数: 233 分
问题陈述
高桥正计划在跳蚤市场设立一个摊位。他有 N 现有商品,以及该商品的售价 i- 第一项是 A_i 日元。
然而,每件商品在出售之前都需要进行包装和展示等准备工作。的准备费用 i- 第一项是 B_i 日元。
高桥可以从 N 待售物品。他可能选择根本不出售任何物品。他可以独立决定是否出售每件物品,但他不能多次出售同一件物品。
当他选择一组项目时 S 出售,利润计算如下:
\text{Profit} = \sum_{i \in S} A_i - \sum_{i \in S} B_i
如果没有选择任何项目,则利润为 0 日元。
求高桥可以获得的最大利润。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq B_i \leq 10^9
- 所有输入值均为整数。
输入
N A_1 B_1 A_2 B_2 \vdots A_N B_N
- 第一行包含一个整数 N,表示项目数。
- 的 i- 以下各项 N 行 (1 \leq i \leq N) 包含售价 A_i 和准备成本 B_i 的 i- 第一项,以空格分隔。
输出
在一行中打印最大利润。
示例输入 1
3 10 3 5 8 7 2
示例输出 1
12
示例输入 2
3 3 5 2 7 1 4
示例输出 2
0
示例输入 3
10 100 50 30 80 200 199 15 15 500 100 60 120 45 30 90 90 300 250 10 1000
示例输出 3
516
示例输入 4
20 1000000000 1 999999999 1000000000 500000000 400000000 300000000 300000001 750000000 250000000 100 200 999999999 999999998 123456789 987654321 800000000 100000000 450000000 450000000 600000000 500000000 50000000 90000000 1 1 700000000 650000000 350000000 400000000 200000000 100000000 888888888 111111111 10 10 500000000 500000001 999999999 2
示例输出 4
4327777774
示例输入 5
1 1 1000000000
示例输出 5
0