#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN = 200000;

int n;
ll x[MAXN];
int val[MAXN];
ll sum[MAXN + 1];

void run() {
	scanf("%d", &n); REP(i, n) scanf("%lld%d", &x[i], &val[i]);
	sum[0] = 0; REP(i, n) sum[i + 1] = sum[i] + val[i];

	// (sum[r+1]-x[r])+(x[l]-sum[l])
	ll lmx = LLONG_MIN, ret = LLONG_MIN;
	REP(i, n) {
		lmx = max(lmx, x[i] - sum[i]);
		ll r = sum[i + 1] - x[i];
		ll cur = lmx + r; if (cur > ret) ret = cur;
	}
	printf("%lld\n", ret);
}

int main() {
	run();
	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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN = 200000;

int n;
ll x[MAXN];
int val[MAXN];
ll sum[MAXN + 1];

void run() {
	scanf("%d", &n); REP(i, n) scanf("%lld%d", &x[i], &val[i]);
	sum[0] = 0; REP(i, n) sum[i + 1] = sum[i] + val[i];

	// (sum[r+1]-x[r])+(x[l]-sum[l])
	ll lmx = LLONG_MIN, ret = LLONG_MIN;
	REP(i, n) {
		lmx = max(lmx, x[i] - sum[i]);
		ll r = sum[i + 1] - x[i];
		ll cur = lmx + r; if (cur > ret) ret = cur;
	}
	printf("%lld\n", ret);
}

int main() {
	run();
	return 0;
}

```