#pragma GCC optimize("O3") #include using namespace std; using ll=long long; using P=pair; template using V=vector; #define fi first #define se second #define all(v) (v).begin(),(v).end() const ll inf=(1e18); //const ll mod=998244353; const ll mod=1000000007; const vector dy={-1,0,1,0},dx={0,-1,0,1}; ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;} ll LCM(ll c,ll d){return c/GCD(c,d)*d;} struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout< bool chmax(T &a, const T &b) { if (a bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } templatevoid debag(const vector &a){cerr<<"debag :";for(auto v:a)cerr<void print(const vector &a){for(auto v:a)cout< struct ST{//1index query l,r lが開区間 using F = function; int n; F f; T ti; vector dat; ST(){}; ST(F f,T ti):f(f),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 query(int a,int b){ 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); } }; int main(){ auto f=[&](P a,P b){ return max(a,b); }; int n; cin>>n; V

a(n); ll sum=0; V num; V

dat; for(int i=0;i>a[i].fi>>a[i].se; sum+=a[i].fi; num.emplace_back(a[i].fi+a[i].se); dat.emplace_back(a[i].fi+a[i].se,a[i].fi); } sort(all(num)); sort(all(dat)); ST

dp(f,P(0,-1)); dp.init(n+5); for(int i=0;i