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