鉴于FlashHu大佬讲的这么好（而且我根本不会）我就不再讲一遍了->

1 //minamoto 2 #include
     
       3 #include
      
        4 #include
       
         5 #define upd(A,L,R) {cmax(A[i][j],A[k][j]+tot[L][R]);\ 6         if(j>=tot[L][R]) cmax(A[i][j],A[k][j-tot[L][R]]);} 7 #define calc(y)    min(x+tot[l][r]+y,Pre[l][x]+suf[r][y]) 8 using namespace std; 9 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)10 char buf[1<<21],*p1=buf,*p2=buf;11 template
        
         inline bool cmax(T&a,const T&b){
   return a
         
          inline int min(T&a,T&b){
   return a
          
           1<<20)Ot();if(x<0)sr[++C]=45,x=-x;27 while(z[++Z]=x%10+48,x/=10);28 while(sr[++C]=z[Z],--Z);sr[++C]='\n';29 }30 const int N=205,M=405,inf=0x3f3f3f3f;31 int s[N],t[N],b[M],tot[M][M],Pre[M][N],suf[M][N],f[M][M];32 int main(){33 //freopen("testdata.in","r",stdin);34 int n=read(),m=0,ans;35 for(int i=1;i<=n;++i){36 b[++m]=s[i]=read();37 b[++m]=t[i]=read()+s[i];38 }39 sort(b+1,b+1+m);40 m=unique(b+1,b+1+m)-b-1;41 for(int i=1;i<=n;++i){42 s[i]=lower_bound(b+1,b+1+m,s[i])-b;43 t[i]=lower_bound(b+1,b+1+m,t[i])-b;44 for(int l=1;l<=s[i];++l)45 for(int r=m;r>=t[i];--r) ++tot[l][r];46 }47 for(int i=1;i<=m;++i) for(int j=1;j<=n;++j)48 Pre[i][j]=suf[i][j]=-inf;49 for(int i=1;i<=m;++i)50 for(int j=0;j<=tot[1][i];++j)51 for(int k=1;k<=i;++k) upd(Pre,k,i);52 for(int i=m;i;--i)53 for(int j=0;j<=tot[i][m];++j)54 for(int k=i;k<=m;++k) upd(suf,i,k);55 for(int l=1;l<=m;++l)56 for(int r=l+1;r<=m;++r)57 for(int y=n,x=0;x<=n;++x){58 int p0=calc(y),p1;59 while(y&&p0<=(p1=calc(y-1))) p0=p1,--y;60 cmax(f[l][r],p0);61 }62 ans=0;63 for(int j=1;j<=n;++j) cmax(ans,min(Pre[m][j],j));64 print(ans);65 for(int i=1;i<=n;++i){66 ans=0;67 for(int l=1;l<=s[i];++l)68 for(int r=m;r>=t[i];--r) cmax(ans,f[l][r]);69 print(ans);70 }71 Ot();72 return 0;73 }