human
CPP solution for "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":


 Write me a Python program to print the value of X?
assistant
#Here is Python program to print the value of X.
 #include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX_N = 1 << 18;
const int INF = 1 << 25;
const ll def = -(1LL << 62);

struct MaxSegTree{
	int n;
	ll dat[2 * MAX_N - 1];
	void init(int n_){
		n = 1;
		while(n < n_) n *= 2;
		for(int i = 0; i < 2 * n - 1; i++) dat[i] = -def;
	}

	void update(int k, ll a){
		k += n - 1;
		dat[k] = a;
		while(k > 0) k = (k - 1) / 2, dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
	}

	ll query(int a, int b){ return query(a, b, 0, 0, n); }

	ll query(int a, int b, int k, int l, int r){
		if(r <= a || b <= l) return def;
		if(a <= l && r <= b) return dat[k];
		ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return max(vl, vr);
	}

	void show(){
		for(int i = 0; i < n; i++) cout << dat[i + n - 1] << " ";
		cout << endl;
	}
} st;

ll x[200000];
ll s[200010];
ll sum[200010];

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
#ifdef LOCAL
	std::ifstream in("in");
	std::cin.rdbuf(in.rdbuf());
#endif

	int N;
	cin >> N;

	st.init(N);
	for(int i = 0; i < N; i++){
		cin >> x[i] >> s[i];
		sum[i + 1] = sum[i] + s[i];
		ll a = sum[i + 1] - x[i];
		//cout << a << endl;
		st.update(i, a);
	}

	ll ans = 0;
	for(int i = 0; i < N; i++){
		ll r = st.query(i, N) + x[i] - sum[i];
		ans = max(ans, r);
	}
	cout << ans << endl;
}