Capture

题意翻译

# 题目大意 在东西方向延伸的细长的森林里栖息着 $N$ 只动物。从森林的最左端到 $p$ 米的地点称为地点 $p$ 。若第i头动物到森林最左端的距离为 $x$(1≤i≤N)那么它就在地点 $x_i$ ,若捕获的话你可以以 $s_i$ 日元卖出。 选择两个整数 $L$ 和 $R$(L≤R),那么,从 $L$ 到 $R$ 范围内的动物就会全部被捕获。但是,买网要花费 $R$-$L$日元,所以你的利益=(被捕获的所有的除物i的合计)-($R$-$L$)日元。 若你只放一次网,得到的最大利益是多少呢? # 输入格式 $x_1$ $s_1$ $x_2$ $s_2$ $:$ $x_N$ $s_N$ # 输出格式 输出最大利益X # 数据范围 1 ≤ $N$ ≤ 2 × $10_5$ 1 ≤ x1 < x2 < ... < $x_N$ ≤ $10_15$ 1 ≤ $s_i$ ≤ $10_9$ 所有输入数据皆为整数.

题目描述

[problemUrl]: https://atcoder.jp/contests/cf17-relay-open/tasks/relay2_f 東西方向に伸びる細長い森に $ N $ 匹のけものが生息しています。以下では、森の西端から $ p $ メートルの地点を地点 $ p $ と呼びます。西から $ i $ 匹目にいるけもの $ (1\ <\ =\ i\ <\ =\ N) $ は地点 $ x_i $ におり、捕獲すると $ s_i $ 円で売れます。 あなたは整数 $ L, $ $ R $ $ (L\ <\ =\ R) $ を選び、地点 $ L $ から地点 $ R $ までの両端を含む範囲、$ [L,\ R] $ に網を放ちます。すると、その範囲内のけものがすべて捕獲されます。ただし、網に $ R\ -\ L $ 円のコストがかかり、あなたの利益は $ ( $捕獲されたすべてのけもの $ i $ に対する $ s_i $ の合計$ )\ -\ (R\ -\ L) $ 円となります。 網を一度だけ放つとき、得られる最大の利益はいくらでしょうか?

输入输出格式

输入格式


入力は以下の形式で標準入力から与えられる。 > $ 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

输入样例 #2

5
10 2
40 5
60 3
70 4
90 1

输出样例 #2

5

输入样例 #3

4
1 100
3 200
999999999999999 150
1000000000000000 150

输出样例 #3

299

说明

### 制約 - $ 1\ <\ =\ N\ <\ =\ 2\ ×\ 10^5 $ - $ 1\ <\ =\ x_1\ <\ x_2\ <\ ...\ <\ x_N\ <\ =\ 10^{15} $ - $ 1\ <\ =\ s_i\ <\ =\ 10^9 $ - 入力値はすべて整数である。 ### Sample Explanation 1 範囲 $ [L\ =\ 40,\ R\ =\ 70] $ に網を放つと西から $ 2, $ $ 3, $ $ 4 $ 匹目のけものを捕獲でき、$ s_2\ +\ s_3\ +\ s_4\ -\ (R\ -\ L)\ =\ 90 $ 円の利益が得られます。$ 91 $ 円以上の利益を得ることはできません。 ### Sample Explanation 2 けものたちは入力例 1 と同じ位置にいますが、彼らの売値が大幅に下がっているため、二匹以上を狙うべきではありません。範囲 $ [L\ =\ 40,\ R\ =\ 40] $ に網を放つことで $ s_2\ -\ (R\ -\ L)\ =\ 5 $ 円の利益が得られ、これが最大です。