Description
NOI2011 在吉林大学开始啦！为了迎接来自全国各地最优秀的信息学选手，
吉林大学决定举办两场盛大的 NOI 嘉年华活动，分在两个不同的地点举办。每
个嘉年华可能包含很多个活动，而每个活动只能在一个嘉年华中举办。
现在嘉年华活动的组织者小安一共收到了 n个活动的举办申请，其中第 i 个
活动的起始时间为 Si，活动的持续时间为Ti。这些活动都可以安排到任意一个嘉
年华的会场，也可以不安排。
小安通过广泛的调查发现，如果某个时刻，两个嘉年华会场同时有活动在进
行（不包括活动的开始瞬间和结束瞬间），那么有的选手就会纠结于到底去哪个
会场，从而变得不开心。所以，为了避免这样不开心的事情发生，小安要求不能
有两个活动在两个会场同时进行（同一会场内的活动可以任意进行）。
另外，可以想象，如果某一个嘉年华会场的活动太少，那么这个嘉年华的吸
引力就会不足，容易导致场面冷清。所以小安希望通过合理的安排，使得活动相
对较少的嘉年华的活动数量最大。
此外，有一些活动非常有意义，小安希望能举办，他希望知道，如果第i 个
活动必须举办（可以安排在两场嘉年华中的任何一个），活动相对较少的嘉年华
的活动数量的最大值。
Input
输入的第一行包含一个整数 n，表示申请的活动个数。
接下来 n 行描述所有活动，其中第 i 行包含两个整数 Si、Ti，表示第 i 个活
动从时刻Si开始，持续 Ti的时间。
Output
输出的第一行包含一个整数，表示在没有任何限制的情况下，活动较少的嘉
年华的活动数的最大值。
接下来 n 行每行一个整数，其中第 i 行的整数表示在必须选择第 i 个活动的
前提下，活动较少的嘉年华的活动数的最大值。
Sample Input
5
8 2
1 5
5 3
3 2
5 3
Sample Output
2
2
1
2
2
2
HINT
在没有任何限制的情况下，最优安排可以在一个嘉年华安排活动 1, 4，而在
另一个嘉年华安排活动 3, 5，活动2不安排。
1≤n≤200 0≤Si≤10^9
1≤Ti≤ 10^9
DP题，首先离散化
首先我们可以想象分配方案应该是交替的一段一段的
所以我们设f[i,j]为时间i前一个会场选j个活动，另一个会场最多有多少活动，那么f[i,j]=max{f[k,j]+s[k,i],f[k,j-s[k,i]]}
然后第一问的答案就是max{min(f[n*2,i],i)}
第二问是要求必选一个，那么我们想像这一个一定在方案中的某一段中
假设区间是(i,j)，那么最优值是g[i,j]，我们预处理出所有的g[i,j]就可以n^3回答所有的询问了
然后我们现在要考虑的是怎么算g[i,j]
因为去掉(i,j)变成左边和右边两部分，所以开始我们dp两次，一个从左边开始一个从右边开始，就可以算g[i,j]了
g[i,j]=max{min(x+y+s[i,j],l[i,x]+r[j,y])}
但是直接枚举是不行的（艹，还让不让人愉快的做题了......）
但是其实x固定，关于y是单峰函数，而且x增大的话，最优值y会减小（因为要尽量平衡），然后就可以x for一遍，y一直递减就行了
所以n^3可以预处理出g[i,j]，然后就做完了（wikioi过不去，又用优化代码过去了233，在我之前没有pascal在wikioi过的）
const
maxn=;
var
a,b:array[..maxn,..]of longint;
s,l,r,f:array[..maxn,..maxn]of longint;
n,k,cnt:longint; procedure up(var x:longint;y:longint);
begin
if x<y then x:=y;
end; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; procedure main;
var
i,j,g,x,y,minx,ans:longint;
begin
read(n);
for i:= to n do
begin
read(a[i,],a[i,]);
inc(a[i,],a[i,]);
end;
while cnt<n<< do
begin
minx:=maxlongint;inc(k);
for i:= to n do
for j:= to do
if (b[i,j]=) and (a[i,j]<minx) then minx:=a[i,j];
for i:= to n do
for j:= to do
if (a[i,j]=minx) and (b[i,j]=) then
begin
inc(cnt);b[i,j]:=;
a[i,j]:=k;
end;
end;
for i:= to n do inc(s[a[i,],a[i,]]);
for i:= to k do
for j:=i+ to k do
inc(s[i,j],s[i,j-]);
for j:= to k do
for i:=j downto do
inc(s[i-,j],s[i,j]);
fillchar(l,sizeof(l),);
fillchar(r,sizeof(r),);
l[,]:=;r[k+,]:=;
for i:= to k do
for j:= to n do
for g:= to i- do
begin
up(l[i,j],l[g,j]+s[g,i]);
if j>=s[g,i] then up(l[i,j],l[g,j-s[g,i]]);
end;
for i:=k downto do
for j:= to n do
for g:=i+ to k+ do
begin
up(r[i,j],r[g,j]+s[i,g]);
if j>=s[i,g] then up(r[i,j],r[g,j-s[i,g]]);
end;
ans:=;
for i:= to n do
up(ans,min(l[k,i],i));
writeln(ans);
for i:= to k do
for j:=i to k do
begin
y:=s[j,k];
for x:= to s[,i] do
begin
while (y>) and (min(x+y-+s[i,j],l[i,x]+r[j,y-])>=min(x+y+s[i,j],l[i,x]+r[j,y])) do dec(y);
up(f[i,j],min(x+y+s[i,j],l[i,x]+r[j,y]));
end;
end;
for i:= to n do
begin
ans:=;
for x:= to a[i,] do
for y:=a[i,] to k do
up(ans,f[x,y]);
writeln(ans);
end;
end; begin
main;
end.