运行一次，每次结果都不一样！

唯一用到时间的地方是 FHQ-Treap 的随机权值，但是看起来很没问题啊？？

请忽略一些调试信息。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct node{int ls,rs,rk,id,maxn,now,tag;}t[N];
mt19937 R(chrono::steady_clock::now().time_since_epoch().count());
int Node(int val,int x){static int cnt=0;t[++cnt]=(node){0,0,R(),x,val-x,val-x,0};return cnt;}
void pushup(int p){
    t[p].maxn=t[p].now;
    if(t[p].ls)t[p].maxn=max(t[p].maxn,t[t[p].ls].maxn);
    if(t[p].rs)t[p].maxn=max(t[p].maxn,t[t[p].rs].maxn);
}
void pushdown(int p){
    if(t[p].tag){
        t[p].id-=t[p].tag;t[p].maxn+=t[p].tag;t[p].now+=t[p].tag;
        if(t[p].ls)t[t[p].ls].tag+=t[p].tag;
        if(t[p].rs)t[t[p].rs].tag+=t[p].tag;
        t[p].tag=0;
    }
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].rk<t[y].rk){pushdown(x);t[x].rs=merge(t[x].rs,y);pushup(x);return x;}
    else{pushdown(y);t[y].ls=merge(x,t[y].ls);pushup(y);return y;}
}
void split(int &x,int &y,int u,int k){
    if(!u)return void(x=y=0);
    pushdown(u);
    if(t[u].id>k){y=u;split(x,t[y].ls,t[u].ls,k);pushup(y);}
    else{x=u;split(t[x].rs,y,t[u].rs,k);pushup(x);}
}
void splitval(int &x,int &y,int u,int k){
    if(!u)return void(x=y=0);
    pushdown(u);
    if(t[u].now>k){y=u;split(x,t[y].ls,t[u].ls,k);pushup(y);}
    else{x=u;split(t[x].rs,y,t[u].rs,k);pushup(x);}
}
int rt;
void Insert(int val,int x){
    int i=Node(val,x),o=0,z=0,r=0;
    split(o,z,rt,x);t[o].tag++;
    splitval(z,r,z,val-x);
    rt=merge(o,merge(i,r));
}
int Query(int x){
    int o=0,z=0,ret1;
    split(o,z,rt,x);
    ret1=t[o].maxn;
    cerr<<"Split:"<<o<<' '<<ret1<<' '<<t[o].    now<<'\n';
    rt=merge(o,z);return ret1;
}
int n,p[N],val[N];
int main(){
    freopen("in.in","r",stdin);freopen("out.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++)cin>>p[i]>>val[i];
    rt=Node(0,0);
    for(int i=n;i;i--){
        int g=Query(p[i])+p[i]+val[i];
        cerr<<g<<'\n';
        ans=max(ans,g);
        Insert(g+1,p[i]);
    }
    cout<<ans;
    return 0;
}