记录编号	7649	评测结果	AAAAAAAAAA
题目名称	地精贸易	最终得分	100
用户昵称	francis	是否通过	通过
代码语言	Pascal	运行时间	1.253 s
提交时间	2008-11-10 21:14:36	内存使用	45.89 MiB

program goblin2;
const
fin='goblin.in';
fou='goblin.out';
var
f,a,c:array[0..4000000]of longint;
k1,k2,w1,c1,w2,c2,num:array[0..100]of longint;
b:array[1..100]of boolean;
n1,n2,x,y,n,m,v,i,j:longint;
f1,f2:text;

procedure init;
begin
assign(f1,fin);
assign(f2,fou);
reset(f1); rewrite(f2);
read(f1,n,m);
for i:=1 to m do
begin
 read(f1,x,y);
 if x<y then begin inc(n1); w1[n1]:=x; c1[n1]:=y-x; k1[n1]:=i; end;
 if x>y  then begin inc(n2); w2[n2]:=y; c2[n2]:=x-y; k2[n2]:=i; b[i]:=true; end;
end;
end;

procedure pr1(x:longint);
begin
inc(num[k1[c[x]]]);
if f[x]=0 then exit
          else pr1(a[x]);
end;

procedure pr2(x:longint);
begin
inc(num[k2[c[x]]]);
if f[x]=0 then exit
          else pr2(a[x]);
end;

procedure main;
begin
for i:=1 to n do
for j:=1 to n1 do
if i-w1[j]>=0 then
 if f[i]<f[i-w1[j]]+c1[j] then
   begin
     f[i]:=f[i-w1[j]]+c1[j];
     a[i]:=i-w1[j];
     c[i]:=j;
   end;
pr1(n);
v:=n+f[n];
fillchar(f,sizeof(f),0);
fillchar(a,sizeof(a),0);
fillchar(c,sizeof(c),0);
for i:=1 to v do
for j:=1 to n2 do
if i-w2[j]>=0 then
 if f[i]<f[i-w2[j]]+c2[j] then
   begin
     f[i]:=f[i-w2[j]]+c2[j];
     a[i]:=i-w2[j];
     c[i]:=j;
   end;
pr2(v);
end;

procedure print;
begin
writeln(f2,v+f[v]-n);
for i:=1 to m do
if num[i]=0 then writeln(f2,'Buy 0')
            else begin
            if b[i]=false then writeln(f2,'Buy ',num[i],' from Alliance')
                          else writeln(f2,'Buy ',num[i],' from Horde');
            end;
close(f1); close(f2);
end;

begin
init;
main;
print;
end.