记录编号	14417	评测结果	AAAAAAAAAA
题目名称	地精贸易	最终得分	100
用户昵称	rottenwood	是否通过	通过
代码语言	Pascal	运行时间	1.037 s
提交时间	2009-10-29 16:14:21	内存使用	23.00 MiB

program goblin;
var
flag:array[0..100] of longint;
fe,ao,buy:array[1..100] of longint;
a,b,c:array[1..100,1..2] of longint;
last,add,f:array[0..2000000] of longint;
i,j,k,m,n,v,w,ans,c1,c2,now:longint;
begin
assign(input,'goblin.in');reset(input);
assign(output,'goblin.out');rewrite(output);
readln(n,m);
for i:=1 to m do
readln(fe[i],ao[i]);
for i:=1 to m do
begin
if fe[i]>ao[i] then flag[i]:=1;
if fe[i]<ao[i] then flag[i]:=0;
end;
for i:=1 to m do
begin
if flag[i]=1 then begin inc(c1);c[c1,1]:=i;a[c1,1]:=ao[i];a[c1,2]:=fe[i]; end;
if flag[i]=0 then begin inc(c2);c[c2,2]:=i;b[c2,1]:=fe[i];b[c2,2]:=ao[i]; end;
end;
fillchar(f,sizeof(f),0);
for i:=1 to c2 do
 for j:=1 to n do
 if b[i,1]<=n then
 if j-b[i,1]>=0 then
 begin
 w:=b[i,1]; v:=b[i,2]-b[i,1];
  if f[j]<f[j-w]+v then
  begin
  f[j]:=f[j-w]+v;
  last[j]:=j-w;
  add[j]:=c[i,2];
  end;
 end;
 j:=n;
 while add[j]<>0 do
  begin
  inc(buy[add[j]]);
  j:=last[j];
  end;
 now:=f[n]+n;
 fillchar(f,sizeof(f),0);
 fillchar(last,sizeof(last),0);
 fillchar(add,sizeof(add),0);
for i:=1 to c1 do
 for j:=1 to now do
 if a[i,1]<=now then
if j-a[i,1]>=0 then
begin
 w:=a[i,1];v:=a[i,2]-a[i,1];
  if f[j]<f[j-w]+v then
  begin
  f[j]:=f[j-w]+v;
  last[j]:=j-w;
  add[j]:=c[i,1];
  end;
 end;
 j:=now;
while add[j]<>0 do
begin
inc(buy[add[j]]);
j:=last[j];
end;
ans:=f[now]+now-n;
writeln(ans);
for i:=1 to m do
if buy[i]<>0 then begin
write('Buy',' ');write(buy[i],' ','from');
if flag[i]=0 then writeln(' ','Alliance') else writeln(' ','Horde');
end
else writeln('Buy 0');
close(output);
end.