#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using lint = long long int; long long int INF = 1001001001001001LL; int inf = 1000000007; long long int MOD = 1000000007LL; double PI = 3.1415926535897932; templateinline void chmin(T1 &a,const T2 &b){if(a>b) a=b;} templateinline void chmax(T1 &a,const T2 &b){if(a struct SegmentTree{ // using F = function // using G = function int n; F f; G g; T ti; vector dat; SegmentTree(){}; SegmentTree(F f,G g,T ti):f(f),g(g),ti(ti){} void init(int n_){ n=1; while(n &v){ int n_=v.size(); init(n_); for(int i=0;i>=1) dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]); } T operator [](int k) const { return dat[k+n]; } T query(int a,int b) const { T vl=ti,vr=ti; for(int l=a+n,r=b+n;l>=1,r>>=1) { if(l&1) vl=f(vl,dat[l++]); if(r&1) vr=f(dat[--r],vr); } return f(vl,vr); } /* TODO わからない 聞く template int find(int a,int b,C &check,int k,int l,int r){ if(!check(dat[k])||r<=a||b<=l) return -1; if(k>=n) return k-n; int m=(l+r)>>1; int vl=find(a,b,check,(k<<1)|0,l,m); if(~vl) return vl; return find(a,b,check,(k<<1)|1,m,r); } template int find(int a,int b,C &check){ return find(a,b,check,1,0,n); }*/ }; int main(){ using T = lint; // type T using E = lint; // type E auto f = [](T a, T b){ // return type T value return a + b; }; auto g = [](T a, E b){ // return type T value return b; // return b; }; T ti = 0; // identify element int n; cin >> n; vector a(n); vector b(n); for(int i = 0; i < n; i++) { int aa, bb; cin >> aa >> bb; a[i] = aa; b[i] = bb; } SegmentTree sg1(f, g, ti); // don't change sg1.build(a); // 初期配列を代入 SegmentTree sg2(f, g, ti); // don't change sg2.build(b); // 初期配列を代入 lint ans = -INF; for(int i = 0; i <= n; i++) { lint homu = sg1.query(0, i) + sg2.query(i, n); lint pura = sg2.query(0, i) + sg1.query(i, n); ans = max(ans, homu - pura); } cout << ans << endl; return 0; }