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

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

#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,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const LL INF = 1e17;

class SegT{
private:
  LL dat[2 * (1 << 18) - 1];
  int NN;

public:
  SegT(int n_){
	NN = 1;
	while(NN < n_) NN <<= 1;
	for(int i=0;i<2*NN-1;++i) dat[i] = -INF;
  }

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

  LL query(int a, int b, int k, int l, int r){
	if(r <= a || b <= l) return -INF;
	if(a <= l && r <= b) return dat[k];
	else{
	  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);
	}
  }
  LL query(int a, int b){
	return query(a, b, 0, 0, NN);
  }
};

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

  int N;
  cin >> N;
  VL xs(N), ss(N);
  SegT seg(N+10);
  VL acc(N+1);

  LL ans = -INF;
  REP(i,N){
	cin >> xs[i] >> ss[i];
	acc[i+1] = acc[i] + ss[i] - (i? xs[i] - xs[i-1]: 0);
	maxi(ans, ss[i]);
	seg.update(i, acc[i]);
  }
  seg.update(N, acc[N]);

  FOR(i,1,N+1){
	maxi(ans, seg.query(i, N+1) - acc[i] + ss[i-1]);
  }
  cout << ans << endl;

  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 VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#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,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const LL INF = 1e17;

class SegT{
private:
  LL dat[2 * (1 << 18) - 1];
  int NN;

public:
  SegT(int n_){
	NN = 1;
	while(NN < n_) NN <<= 1;
	for(int i=0;i<2*NN-1;++i) dat[i] = -INF;
  }

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

  LL query(int a, int b, int k, int l, int r){
	if(r <= a || b <= l) return -INF;
	if(a <= l && r <= b) return dat[k];
	else{
	  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);
	}
  }
  LL query(int a, int b){
	return query(a, b, 0, 0, NN);
  }
};

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

  int N;
  cin >> N;
  VL xs(N), ss(N);
  SegT seg(N+10);
  VL acc(N+1);

  LL ans = -INF;
  REP(i,N){
	cin >> xs[i] >> ss[i];
	acc[i+1] = acc[i] + ss[i] - (i? xs[i] - xs[i-1]: 0);
	maxi(ans, ss[i]);
	seg.update(i, acc[i]);
  }
  seg.update(N, acc[N]);

  FOR(i,1,N+1){
	maxi(ans, seg.query(i, N+1) - acc[i] + ss[i-1]);
  }
  cout << ans << endl;

  return 0;
}

```