记录编号	7543	评测结果	AAAAAAAAAA
题目名称	地精贸易	最终得分	100
用户昵称	elysian	是否通过	通过
代码语言	Pascal	运行时间	1.261 s
提交时间	2008-11-10 17:00:56	内存使用	76.41 MiB

program elysian;
type
node=record
x,y:longint;
end;
const
fin='goblin.in';fout='goblin.out';
var
n,m,ans1,ans2,last:longint;
w,c,f:array[0..4000000] of longint;
pre:array[0..4000000] of node;
flag,d:array[0..100] of integer;
f1,f2:text;



procedure main1;
var
i,j:longint;
begin
for i:=1 to m do
if flag[i]=1 then
begin
 for j:=0 to n do
  begin
    if j-c[i]>=0 then { f[j]:=max(f[j],f[j-c[i]]+w[i])}
     if f[j-c[i]]+w[i]>f[j] then
      begin
        f[j]:=f[j-c[i]]+w[i];
        pre[j].x:=j-c[i];
        pre[j].y:=i;
      end;
  end;
end;
ans1:=f[n];
last:=n;

end;

procedure main2;
var
i,j:longint;
begin
for i:=1 to m do
if flag[i]=2 then
begin
 for j:=0 to n do
  begin
   if j-c[i]>=0 then { f[j]:=max(f[j],f[j-c[i]]+w[i])}
     if f[j-c[i]]+w[i]>f[j] then
      begin
        f[j]:=f[j-c[i]]+w[i];
        pre[j].x:=j-c[i];
        pre[j].y:=i;
      end;
  end;
end;
ans2:=f[n];
last:=n;
end;

procedure search;
var
i,j,t1,t2:longint;
begin
i:=last;
repeat
t1:=pre[i].x;
t2:=pre[i].y;
inc(d[t2]);
i:=t1;
until i<=0;

end;

procedure print;
var
i:longint;
begin
assign(f2,fout);rewrite(f2);
writeln(f2,ans1+ans2);
for i:=1 to m do
if (flag[i]=1)and(d[i]>0) then writeln(f2,'Buy ',d[i],' from Alliance')
else if (flag[i]=2)and(d[i]>0) then writeln(f2,'Buy ',d[i],' from Horde')
else if d[i]=0 then writeln(f2,'Buy 0');
close(f2);

end;

procedure init;
var
i,j,t1,t2:longint;
begin
assign(f1,fin);reset(f1);
readln(f1,n,m);
for i:=1 to m do
begin
readln(f1,t1,t2);
if t2>t1 then begin flag[i]:=1;c[i]:=t1;w[i]:=t2-t1;end;
if t1>t2 then begin flag[i]:=2;c[i]:=t2;w[i]:=t1-t2;end;
end;
close(f1);
end;

begin
init;
ans1:=0;
main1;
fillchar(d,sizeof(d),0);
search;
n:=n+ans1;
fillchar(pre,sizeof(pre),0);
ans2:=0;
fillchar(f,sizeof(f),0);
main2;
search;
print;
end.