$$pre_{i,j}=\max\limits_{k=1}^{i}{pre_{k,j}+tot_{k,i},pre_{k,j-tot_{k,i}}}$$

$$f_{i,j}=\max\limits_{x=1}^{m}\max\limits_{y=1}^{m}{\min(x+tot_{i,j}+y,pre_{i,x}+suf_{j,y})}$$

### Code:

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define F(i,j,k) for((i)=(j);(i)<=(k);++i)
#define R(i,j,k) for((i)=(j);(i)>=(k);--i)

const int N=4e2+9;
const int inf=1e9+9;

int n,m,i,j,k,l,r,s[N],t[N],b[N];
int tot[N][N],pre[N][N],suf[N][N],f[N][N];

inline int IN() {
char ch;bool flag=0;int x=0;
while(ch=getchar(),!isdigit(ch)) if(ch=='-') flag=1;
while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
if(flag) x=-x;return x;
}

inline int calc(int x,int y)
{return min(x+tot[l][r]+y,pre[l][x]+suf[r][y]);}

int main() {
n=IN();
F(i,1,n) b[++m]=s[i]=IN(),b[++m]=t[i]=IN()+s[i];
sort(b+1,b+1+m),
m=unique(b+1,b+1+m)-b-1;/*离散化去重*/
F(i,1,n) {
s[i]=lower_bound(b+1,b+1+m,s[i])-b;
t[i]=lower_bound(b+1,b+1+m,t[i])-b;
F(l,1,s[i]) R(r,m,t[i]) ++tot[l][r];/*计算出 tot*/
}
F(i,1,m) F(j,1,n) pre[i][j]=suf[i][j]=-inf;/*初始化*/
/*----------计算出 pre 和 suf----------*/
F(i,1,m) F(j,0,tot[1][i]) F(k,1,i) {
pre[i][j]=max(pre[i][j],pre[k][j]+tot[k][i]);
if(j>=tot[k][i]) pre[i][j]=max(pre[i][j],pre[k][j-tot[k][i]]);
}
R(i,m,1) F(j,0,tot[i][m]) F(k,i,m) {
suf[i][j]=max(suf[i][j],suf[k][j]+tot[i][k]);
if(j>=tot[i][k]) suf[i][j]=max(suf[i][j],suf[k][j-tot[i][k]]);
}
/*计算 f*/
F(l,1,m) F(r,l+1,m) for(int y=n,x=0;x<=n;++x) {/*y 当做指针扫一遍*/
int old_calc=calc(x,y),new_calc;
while(y&&old_calc<=(new_calc=calc(x,y-1))) --y,old_calc=new_calc;
f[l][r]=max(f[l][r],calc(x,y));/*转移*/
}
/*输出答案*/
int ans=0;
F(i,1,n) ans=max(ans,min(pre[m][i],i));
printf("%d\n",ans);/*第一问*/
F(i,1,n) {
ans=0;
F(l,1,s[i]) R(r,m,t[i]) ans=max(ans,f[l][r]);
printf("%d\n",ans);/*第二问*/
}return 0;
}


QAQ