Description
小PP对广大的矿泉水都爱的深沉。不过他对每个牌子的矿泉水都有不同的喜爱值。比如说对于第i种矿泉水，小PP对它的喜欢值为Ai。如果他在第k天喝了瓶第i种牌子的矿泉水，那么他在k+Ai天前（包括第k+Ai天）必须再喝一瓶这种牌子的矿泉水，否则就会精神失常。（Hint：如果第i种矿泉水的Ai=1，则小PP天天都要喝这种矿泉水，不然就会精神失常）。
可是小PP又有个很奇怪得癖好，一天只喝一个牌子的水，或者他不喝。在第1天前，小PP因为太渴，把所有牌子（除了Evian）的矿泉水都喝了个遍。
当然，每种牌子的矿泉水的价格都是不同的。不过这些牌子中有个叫Evian的牌子，喝他一次，便能得到永生。不过Evian超贵，一般人是喝不起的。但是唯一的希望是某个钱人送他一瓶。
而这个有钱人将在特定的一天出现，他的出现，会带给小PP永生。若第i天小PP喝任何牌子的水都会精神失常，则认定：小PP最多正常i-1天。当然，小PP也是爱钱的，若他第i天不管喝任何水（不包括Evian）都会精神失常，那么，他在第i天是不会喝水的。（简单的说，先要命，后要钱）
Input
第一行：n,m,q 表示共n种矿泉水，cp将在第m天出现，并送小PP一瓶Evian.（只要撑到第m天，即安全度过第m-1天，即可得到永生）
小PP初始有q块大洋。
第二行n个数： 表示喜爱值Ai
第三行n个数： 表示第i个牌子的矿泉水单价 Ci元（这里的矿泉水不包含Evian）
Output
若小PP能得到永生，则
第一行：输出“+oo”（不含引号）。
第二行：输出得到永生时小PP能剩下的最多钱数。
否则，如果小PP不能得到永生，则
第一行：输出小PP最多能精神正常得天数NMAX（就是不精神失常的天数）。
第二行：输出小PP正常活到NMAX天能剩下的最多钱数。
Sample Input
【输入样例1】
4 4 1000
3 3 3 3
1 1 1 1
【输入样例2】
4 3 1000
3 3 3 3
1 1 1 1
【输入样例3】
2 4 7
2 3
1 1
Sample Output
【输出样例1】
2
1000
【输出样例2】
+oo
1000
【输出样例3】
+oo
5
Hint
【数据规模】
50% n<=3
80% A4<=4
100% n<=4 q，Ci<=maxlongint m<=1000 Ai<=9
算法讨论
五维dp，f[i,j,k,e,r]表示在第i天是j天内必须和第一种水，后面同理，第i天可以不和或者喝任意一种水，所以上一次喝某种水且能活到今天的日期内买这种水。
varf:array[0..1100,0..9,0..9,0..9,0..9] of longint;x,y:array[0..10] of longint;n,m,q,i,j:longint;
function min(x,y:longint):longint;
beginif x>y then exit(y);exit(x);
end;
procedure chp;
vara:array[0..1000,0..9] of longint;p:longint;
beginfillchar(a,sizeof(a),$7);a[0,x[1]]:=0;for i:=1 to m dobeginfor j:=0 to x[1]-1 doa[i,j]:=min(a[i-1,j+1],a[i,j]);for j:=1 to x[1] doif i-j>=0 thena[i,x[1]]:=min(a[i,i-j]+y[1],a[i,x[1]]);end;p:=maxlongint;for i:=0 to x[1] dop:=min(p,a[m,i]);writeln('+oo');writeln(q-p);
end;
procedure xi;
vara:array[0..1000,0..9,0..9] of longint;tot,ans,k,l:longint;p:boolean;
beginfillchar(a,sizeof(a),$7);a[0,x[1],x[2]]:=0;for i:=1 to m-1 dobeginp:=false;ans:=tot;tot:=maxlongint;for j:=1 to x[1] dofor k:=1 to x[2] dobegina[i,j,k]:=a[i-1,j+1,k+1];for l:=1 to x[1] doa[i,j,k]:=min(a[i,j,k],a[i-1,l,k+1]+y[1]);for l:=1 to x[2] doa[i,j,k]:=min(a[i,j,k],a[i-1,j+1,l]+y[2]);if (j>0)and(k>0) thenbeginif a[i,j,k]<=q then p:=true;if a[i,j,k]<tot then tot:=a[i,j,k];end;end;if p=false thenbeginwriteln(i-1);writeln(q-ans);halt;end;end;writeln('+oo');writeln(q-tot);
end;
procedure huan;
vara:array[0..1000,0..9,0..9,0..9] of longint;tot,ans,k,l,e:longint;p:boolean;
beginfillchar(a,sizeof(a),$7);a[0,x[1],x[2],x[3]]:=0;for i:=1 to m-1 dobeginp:=false;ans:=tot;tot:=maxlongint;for j:=1 to x[1] dofor k:=1 to x[2] dofor e:=1 to x[3] dobegina[i,j,k,e]:=a[i-1,j+1,k+1,e+1];for l:=1 to x[1] doa[i,j,k,e]:=min(a[i,j,k,e],a[i-1,l,k+1,e+1]+y[1]);for l:=1 to x[2] doa[i,j,k,e]:=min(a[i,j,k,e],a[i-1,j+1,l,e+1]+y[2]);for l:=1 to x[3] doa[i,j,k,e]:=min(a[i,j,k,e],a[i-1,j+1,k+1,l]+y[3]);if (j>0)and(k>0)and(e>0) thenbeginif a[i,j,k,e]<=q then p:=true;if a[i,j,k,e]<tot then tot:=a[i,j,k,e];end;end;if p=false thenbeginwriteln(i-1);writeln(q-ans);halt;end;end;writeln('+oo');writeln(q-tot);
end;
procedure zxy;
vartot,ans,k,l,e,r:longint;p:boolean;
beginfillchar(f,sizeof(f),$7);f[0,x[1],x[2],x[3],x[4]]:=0;for i:=1 to m-1 dobeginp:=false;ans:=tot;tot:=maxlongint;for j:=1 to x[1] dofor k:=1 to x[2] dofor e:=1 to x[3] dofor r:=1 to x[4] dobeginf[i,j,k,e,r]:=f[i-1,j+1,k+1,e+1,r+1];for l:=1 to x[1] dof[i,j,k,e,r]:=min(f[i,j,k,e,r],f[i-1,l,k+1,e+1,r+1]+y[1]);for l:=1 to x[2] dof[i,j,k,e,r]:=min(f[i,j,k,e,r],f[i-1,j+1,l,e+1,r+1]+y[2]);for l:=1 to x[3] dof[i,j,k,e,r]:=min(f[i,j,k,e,r],f[i-1,j+1,k+1,l,r+1]+y[3]);for l:=1 to x[4] dof[i,j,k,e,r]:=min(f[i,j,k,e,r],f[i-1,j+1,k+1,e+1,l]+y[4]);if (j>0)and(k>0)and(e>0)and(r>0) thenbeginif f[i,j,k,e,r]<=q then p:=true;if f[i,j,k,e,r]<tot then tot:=f[i,j,k,e,r];end;end;if p=false thenbeginwriteln(i-1);writeln(q-ans);halt;end;end;writeln('+oo');writeln(q-tot);
end;
beginreadln(n,m,q);for i:=1 to n doread(x[i]);for i:=1 to n doread(y[i]);if n=1 then chp;if n=2 then xi;if n=3 then huan;if n=4 then zxy;
end.