#include <bits/stdc++.h>
using namespace std;

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/12/04  Problem: codefestival2017_team_relay F / Link: __CONTEST_URL__  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

/*-----------------
Segment tree (merge)
点更新及び区間評価 Ｏ(logN)
0-index
書き換え時はmerge、初期値とクエリ返却値に注意
--------------------*/
template<typename type>
struct SegTree {
	type INIT_VAL = -1e17; // 影響のない値
	inline type merge(type a, type b) { //台数構造

		return max(a, b); //merge部分

	}
	//-----setting-----//
	int N;	vector<type> dat;

	SegTree(int _N) {
		N = 1;
		while (N < _N)N *= 2;
		dat = vector<type>(N * 2 - 1, INIT_VAL);
		//dat.resize(N * 2 - 1, INT_MAX);
		// max値を入れておく、書き換えupdasteはいいが加算addに注意
	}
	SegTree(vector<type> &a, int _N) {//なにかしらで初期化できるならする。(クエリが後でも処理できるときなど)
		N = 1;
		while (N < _N)N *= 2;
		dat = vector<type>(N * 2 - 1, INIT_VAL);
		for (int i = 0; i < _N; ++i)dat[i + N - 1] = a[i];
		build();
	}
	~SegTree() { vector<type>().swap(dat); }

	void build() { for (int i = N - 2; i >= 0; i--) dat[i] = merge(dat[2 * i + 1], dat[2 * i + 2]); }

	void add(int k, type val) {
		k += N - 1;
		dat[k] += val;
		while (k) { // 根まで再帰的に上る
			k = (k - 1) / 2;
			dat[k] = merge(dat[k * 2 + 1], dat[k * 2 + 2]); // 結果をmerge
		}
	}

	void update(int k, type val) {
		k += N - 1;
		dat[k] = val;
		while (k) { // 根まで再帰的に上る
			k = (k - 1) / 2;
			dat[k] = merge(dat[k * 2 + 1], dat[k * 2 + 2]); // merge
		}
	}
	// 区間[a,b)の評価
	type query(int a, int b, int k, int l, int r) {
		//if (r == -1)r = N;
		if (r <= a || b <= l)return INIT_VAL; // 区間が被らない 
		if (a <= l&&b >= r)return dat[k]; // 値を返す
		type v1 = query(a, b, k * 2 + 1, l, (l + r) / 2);
		type v2 = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return merge(v1, v2); //merge
	}

	inline type query(int a, int b) {
		return query(a, b, 0, 0, N);
	}
};



LL N;

LL ans = 0LL;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> N;
	SegTree<LL> seg(N+10);
	VL x(N,0); VL s(N,0);
	VL cum(N+1,0);
	FOR(i,0,N){
		cin>>x[i]>>s[i];	
		cum[i+1]= cum[i] + s[i] -(i>0?x[i]-x[i-1]:0);
		//debug(cum[i+1]);
		ans =max(ans,s[i]);
		seg.update(i,cum[i+1]);
	}
	FOR(i,0,N){
		LL ret = seg.query(i,N) - (cum[i+1])+ (s[i]);
		//debug(ret);
		ans=max(ans,ret);
	}
	
	cout << ans << "\n";

	return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

In a long narrow forest stretching east-west, there are N beasts. Below, we will call the point that is p meters from the west end Point p. The i-th beast from the west (1 ≤ i ≤ N) is at Point x_i, and can be sold for s_i yen (the currency of Japan) if captured.

You will choose two integers L and R (L ≤ R), and throw a net to cover the range from Point L to Point R including both ends, [L, R]. Then, all the beasts in the range will be captured. However, the net costs R - L yen and your profit will be (the sum of s_i over all captured beasts i) - (R - L) yen.

What is the maximum profit that can be earned by throwing a net only once?

Constraints

* 1 ≤ N ≤ 2 × 10^5
* 1 ≤ x_1 < x_2 < ... < x_N ≤ 10^{15}
* 1 ≤ s_i ≤ 10^9
* All input values are integers.

Input

Input is given from Standard Input in the following format:


N
x_1 s_1
x_2 s_2
:
x_N s_N


Output

When the maximum profit is X yen, print the value of X.

Examples

Input

5
10 20
40 50
60 30
70 40
90 10


Output

90


Input

5
10 2
40 5
60 3
70 4
90 1


Output

5


Input

4
1 100
3 200
999999999999999 150
1000000000000000 150


Output

299

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2017/12/04  Problem: codefestival2017_team_relay F / Link: __CONTEST_URL__  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

/*-----------------
Segment tree (merge)
点更新及び区間評価 Ｏ(logN)
0-index
書き換え時はmerge、初期値とクエリ返却値に注意
--------------------*/
template<typename type>
struct SegTree {
	type INIT_VAL = -1e17; // 影響のない値
	inline type merge(type a, type b) { //台数構造

		return max(a, b); //merge部分

	}
	//-----setting-----//
	int N;	vector<type> dat;

	SegTree(int _N) {
		N = 1;
		while (N < _N)N *= 2;
		dat = vector<type>(N * 2 - 1, INIT_VAL);
		//dat.resize(N * 2 - 1, INT_MAX);
		// max値を入れておく、書き換えupdasteはいいが加算addに注意
	}
	SegTree(vector<type> &a, int _N) {//なにかしらで初期化できるならする。(クエリが後でも処理できるときなど)
		N = 1;
		while (N < _N)N *= 2;
		dat = vector<type>(N * 2 - 1, INIT_VAL);
		for (int i = 0; i < _N; ++i)dat[i + N - 1] = a[i];
		build();
	}
	~SegTree() { vector<type>().swap(dat); }

	void build() { for (int i = N - 2; i >= 0; i--) dat[i] = merge(dat[2 * i + 1], dat[2 * i + 2]); }

	void add(int k, type val) {
		k += N - 1;
		dat[k] += val;
		while (k) { // 根まで再帰的に上る
			k = (k - 1) / 2;
			dat[k] = merge(dat[k * 2 + 1], dat[k * 2 + 2]); // 結果をmerge
		}
	}

	void update(int k, type val) {
		k += N - 1;
		dat[k] = val;
		while (k) { // 根まで再帰的に上る
			k = (k - 1) / 2;
			dat[k] = merge(dat[k * 2 + 1], dat[k * 2 + 2]); // merge
		}
	}
	// 区間[a,b)の評価
	type query(int a, int b, int k, int l, int r) {
		//if (r == -1)r = N;
		if (r <= a || b <= l)return INIT_VAL; // 区間が被らない 
		if (a <= l&&b >= r)return dat[k]; // 値を返す
		type v1 = query(a, b, k * 2 + 1, l, (l + r) / 2);
		type v2 = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return merge(v1, v2); //merge
	}

	inline type query(int a, int b) {
		return query(a, b, 0, 0, N);
	}
};



LL N;

LL ans = 0LL;

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> N;
	SegTree<LL> seg(N+10);
	VL x(N,0); VL s(N,0);
	VL cum(N+1,0);
	FOR(i,0,N){
		cin>>x[i]>>s[i];	
		cum[i+1]= cum[i] + s[i] -(i>0?x[i]-x[i-1]:0);
		//debug(cum[i+1]);
		ans =max(ans,s[i]);
		seg.update(i,cum[i+1]);
	}
	FOR(i,0,N){
		LL ret = seg.query(i,N) - (cum[i+1])+ (s[i]);
		//debug(ret);
		ans=max(ans,ret);
	}
	
	cout << ans << "\n";

	return 0;
}

```