记录编号	7783	评测结果	AAAAAAAAAA
题目名称	[BYVoid S3] 阿鲁高的远航	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.332 s
提交时间	2008-11-11 18:31:13	内存使用	1.28 MiB

program cch(input,output);
var
 t,v,a,w,i,j,x:longint;
 n,b:array[1..1000] of longint;
 f,from,ans:array[1..1001,0..100] of longint;

function max(x,y:longint):longint;
begin
 if x>y then exit(x)
  else exit(y);
end;

function min(x,y:longint):longint;
begin
 if x<y then exit(x)
  else exit(y);
end;

begin
 assign(input,'sail.in');
 assign(output,'sail.out');
 reset(input);
 rewrite(output);
 readln(t,v,a,w);
 for i:=1 to t do readln(n[i],b[i]);
 for i:=0 to v do f[t+1,i]:=0;
 for i:=t downto 1 do
  for j:=0 to v do
   begin
    f[i,j]:=100000000;
    for x:=max(n[i]-j,0) to min(a,v+n[i]-j) do
     if f[i,j]>f[i+1,j+x-n[i]]+b[i]*x+w*(j+x-n[i]) then
      begin
       ans[i,j]:=x; from[i,j]:=j+x-n[i];
       f[i,j]:=f[i+1,j+x-n[i]]+b[i]*x+w*(j+x-n[i]);
      end;
   end;
 writeln(f[1,0]);
 writeln(ans[1,0]);
 j:=0;
 for i:=2 to t do
  begin
   j:=from[i-1,j];
   writeln(ans[i,j]);
  end;
 close(input);
 close(output);
end.