← 返回题目列表

AtCoder · relay2_f

F. 捕捉

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

分数: 100 点

问题陈述

在一片东西向延伸的狭长森林里,有 N 野兽。下面,我们将这个点称为 p 距西端米 p。的 i-来自西方的野兽 (1 ≤ i ≤ N) 位于点 x_i,并且可以出售 s_i 日元(日本货币)(如果捕获)。

您将选择两个整数 L 和 R (L ≤ R),并撒网覆盖 Point 的范围 L 指向 R 包括两端, [L, R]。届时,范围内的所有凶兽都会被捕获。然而,净成本 R - L 日元,您的利润将为 (总和 s_i 超过所有捕获的野兽 i) - (R - L) 日元。

只撒一次网最多能获得多少利润?

约束

  • 1 ≤ N ≤ 2 × 10^5
  • 1 ≤ x_1 < x_2 < ... < x_N ≤ 10^{15}
  • 1 ≤ s_i ≤ 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
x_1 s_1
x_2 s_2
:
x_N s_N

输出

当最大利润为 X 日元,打印值 X.


示例输入 1

5
10 20
40 50
60 30
70 40
90 10

示例输出 1

90

如果你撒网覆盖范围 [L = 40, R = 70],西边的第二只、第三只、第四只猛兽将被捕获,产生的利润为 s_2 + s_3 + s_4 - (R - L) = 90 日元。是不可能赚到的 91 日元以上。


示例输入 2

5
10 2
40 5
60 3
70 4
90 1

示例输出 2

5

野兽的位置与样本1相同,但售价大幅下降,因此不应瞄准两只或更多野兽。通过撒网覆盖范围 [L = 40, R = 40],您可以赚取 s_2 - (R - L) = 5 日元,这是最大可能的利润。


示例输入 3

4
1 100
3 200
999999999999999 150
1000000000000000 150

示例输出 3

299