← 返回题目列表

AtCoder · awc0090_a

A. 跳蚤市场摊位规划

中文机器翻译题面 查看原题

分数: 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