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

program sail;
const
fin='sail.in';
fou='sail.out';
max=2000000000;
var
f,p,q:array[0..1000,0..100]of longint;
a,b,c:array[1..1000]of longint;
x,min,k,m,n,v,t,i,j:longint;
f1,f2:text;

procedure init;
begin
assign(f1,fin);
assign(f2,fou);
reset(f1); rewrite(f2);
read(f1,t,v,n,m);
for i:=1 to t do
read(f1,a[i],b[i]);
for i:=0 to t do
for j:=0 to v do
f[i,j]:=max;
f[0,0]:=0;
end;

procedure main;
begin
for i:=1 to t do
for j:=0 to v do
for k:=0 to n do
if (j+a[i]-k>=0)and(j+a[i]-k<=v) then
 if f[i-1,j+a[i]-k]+k*b[i]+(j+a[i]-k)*m<f[i,j] then
    begin
      f[i,j]:=f[i-1,j+a[i]-k]+k*b[i]+(j+a[i]-k)*m;
      p[i,j]:=j+a[i]-k;
      q[i,j]:=k;
    end;
end;

procedure pri(x,y:longint);
begin
if y=0 then exit;
c[y]:=q[y,x];
pri(p[y,x],y-1);
end;

procedure print;
begin
min:=max;
for i:=0 to v do
if min>f[t,i] then begin min:=f[t,i]; x:=i; end;
pri(x,t);
writeln(f2,min);
for i:=1 to t do
writeln(f2,c[i]);
close(f1); close(f2);
end;

begin
init;
main;
print;
end.