记录编号	14794	评测结果	AAAAAAAAAA
题目名称	[BYVoid S3] 阿鲁高的远航	最终得分	100
用户昵称	打不死的羊	是否通过	通过
代码语言	Pascal	运行时间	0.963 s
提交时间	2009-11-04 18:55:25	内存使用	6.62 MiB

program sail;
type
fxz1=array[1..1000,0..400] of longint;
fxz2=array[1..1000,0..400] of boolean;
fxz3=array[1..1000]of longint;
var
f1,f2:text;
i,j,k,min,t,w,a,v,ls:longint;
ans,way,qian,num:fxz1;
flag:fxz2;
need,mana:fxz3;

      procedure shu(i,j:longint);
      begin if qian[i,j]<>-1 then shu(i-1,qian[i,j]);
            writeln(f2,num[i,j]);
      end;

begin assign(f1,'sail.in');
      assign(f2,'sail.out');
      reset(f1);rewrite(f2);
      readln(f1,t,v,a,w);
      for i:=1 to t do readln(f1,need[i],mana[i]);
      for i:=1 to t do
      for j:=0 to 400 do begin ans[i,j]:=maxlongint;
                               flag[i,j]:=false;
                        end;

      flag[1,0]:=true;ans[1,0]:=0;
      for i:=1 to a do
      for j:=v+need[1] downto 0 do
      if (flag[1,j])and(j+1<=v+need[1])and(ans[1,j]+mana[1]<ans[1,j+1]) then
      begin ans[1,j+1]:=ans[1,j]+mana[1];
            flag[1,j+1]:=true;
      end;
      for j:=need[1] to need[1]+v do begin ans[1,j-need[1]]:=ans[1,j];
                                           flag[1,j-need[1]]:=true;
                                           flag[1,j]:=false;
                                      end;

      for j:=0 to v do begin num[1,j]:=j+need[1];qian[1,j]:=-1;end;
      for i:=2 to t do
      begin for j:=0 to v do
            begin if ans[i-1,j]<>maxlongint then ans[i,j]:=ans[i-1,j]+j*w
                                            else ans[i,j]:=maxlongint;
                  flag[i,j]:=flag[i-1,j];
                  qian[i,j]:=j
            end;
            for k:=1 to a do
            for j:=v+need[i] downto 0 do
            if (flag[i,j])and(ans[i,j]<>maxlongint) then
            if  ans[i,j]+mana[i]<ans[i,j+1] then
                                               begin ans[i,j+1]:=ans[i,j]+mana[i];
                                                     flag[i,j+1]:=true;
                                                     qian[i,j+1]:=qian[i,j];
                                                end;
            for j:=need[i] to v+need[i] do begin ans[i,j-need[i]]:=ans[i,j];
                                                 flag[i,j-need[i]]:=true;
                                                 flag[i,j]:=false;
                                                 qian[i,j-need[i]]:=qian[i,j];
                                           end;
            for j:=0 to v do num[i,j]:=need[i]+j-qian[i,j];
      end;
      min:=maxlongint;
      for i:=0 to v do if ans[t,i]<min then begin min:=ans[t,i];ls:=i;end;
      writeln(f2,min);
      shu(t,ls);
      close(f1);close(f2);
end.