配点 : $100$ 点

問題文

東西方向に伸びる細長い森に $N$ 匹のけものが生息しています。以下では、森の西端から $p$ メートルの地点を地点 $p$ と呼びます。西から $i$ 匹目にいるけもの $(1 \leq i \leq N)$ は地点 $x_i$ におり、捕獲すると $s_i$ 円で売れます。

あなたは整数 $L,$ $R$ $(L \leq R)$ を選び、地点 $L$ から地点 $R$ までの両端を含む範囲、$[L, R]$ に網を放ちます。すると、その範囲内のけものがすべて捕獲されます。ただし、網に $R - L$ 円のコストがかかり、あなたの利益は $($捕獲されたすべてのけもの $i$ に対する $s_i$ の合計$) - (R - L)$ 円となります。

網を一度だけ放つとき、得られる最大の利益はいくらでしょうか？

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq x_1 < x_2 < ... < x_N \leq 10^{15}$
• $1 \leq s_i \leq 10^9$
• 入力値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$x_1$ $s_1$

$x_2$ $s_2$

$:$

$x_N$ $s_N$

出力

得られる最大の利益が $X$ 円のとき、$X$ の値を出力せよ。

5
10 20
40 50
60 30
70 40
90 10

90

範囲 $[L = 40, R = 70]$ に網を放つと西から $2,$ $3,$ $4$ 匹目のけものを捕獲でき、$s_2 + s_3 + s_4 - (R - L) = 90$ 円の利益が得られます。$91$ 円以上の利益を得ることはできません。

5
10 2
40 5
60 3
70 4
90 1

5

けものたちは入力例 1 と同じ位置にいますが、彼らの売値が大幅に下がっているため、二匹以上を狙うべきではありません。範囲 $[L = 40, R = 40]$ に網を放つことで $s_2 - (R - L) = 5$ 円の利益が得られ、これが最大です。

4
1 100
3 200
999999999999999 150
1000000000000000 150

299