记录编号	7832	评测结果	AAAAAAAAAA
题目名称	[BYVoid S3] 阿鲁高的远航	最终得分	100
用户昵称	elysian	是否通过	通过
代码语言	Pascal	运行时间	0.762 s
提交时间	2008-11-11 20:51:52	内存使用	1.83 MiB

program elysian;
type
node=record
x,y:longint;
end;
const
fin='sail.in';fout='sail.out';
var
f1,f2:text;
f:array[1..1010,0..110] of int64;
pre:array[1..1010,0..110] of node;
d:array[0..1010] of longint;
n,sp:array[0..1000] of longint;

t,v,a,w:longint;
procedure init;
var
i,j:longint;

begin
assign(f1,fin);reset(f1);
readln(f1,t,v,a,w);
for i:=1 to t do
readln(f1,n[i],sp[i]);
close(f1);
for i:=2 to t+1 do
for j:=0 to v do
begin
 if i=2 then
  begin
    f[2,j]:=(n[1]+j)*sp[1]+j*w;
    pre[2,j].x:=0;
    pre[2,j].y:=n[1]+j;
  end

  else f[i,j]:=maxlongint-1000;
end;

end;

procedure main;
var
k,s,x,spre,i,j:longint;
begin
for k:=3 to t+1 do
for s:=0 to v do  //f[k,s]:=min{ f[k-1,s+n[k-1]-x]+x*sp[k-1]+w*(s-x+n[k-1])
 for x:=0 to a do
  begin
   if (s+n[k-1]-x>=0)and(s+n[k-1]-x<=v) then
   if f[k-1,s+n[k-1]-x]+x*sp[k-1]+w*s<f[k,s] then
   begin
   f[k,s]:=f[k-1,s+n[k-1]-x]+x*sp[k-1]+w*s;
   pre[k,s].x:=s+n[k-1]-x;
   pre[k,s].y:=x;
  end;

 end;
assign(f2,fout);rewrite(f2);
writeln(f2,f[t+1,0]);
i:=0;j:=t+1;
repeat
d[j-1]:=pre[j,i].y;
i:=pre[j,i].x;
dec(j);
until j<2;
for i:=1 to t do writeln(f2,d[i]);
close(f2);
end;

begin
init;
main;
end.