记录编号	7668	评测结果	AAAAAAAAAA
题目名称	地精贸易	最终得分	100
用户昵称	lc	是否通过	通过
代码语言	Pascal	运行时间	1.386 s
提交时间	2008-11-10 22:40:10	内存使用	11.56 MiB

program goblin;

 var
     f:array[0..1000000] of longint;
     gf,gk:array[0..1000000] of longint;
     w1,w2:array[1..100] of longint;
     n,m,i,pn:longint;
     ans:array[1..100] of longint;

procedure init;
 var
     i,j:longint;
 begin
   readln(n,m);
   pn:=n;
   for i:=1 to m do
   read(w1[i],w2[i]);
 end;

procedure total(v:longint);

 begin
   while gk[v]<>0 do
    begin
     inc(ans[gk[v]]);
     v:=gf[v];
    end;
 end;

procedure solve1;
  var
     i,j,tm:longint;

 begin

   for i:=0 to n do
    for j:=1 to m do
     begin
      if i<w1[j] then continue;
      if w1[j]>=w2[j] then continue;
      tm:=f[i-w1[j]]+w2[j]-w1[j];
      if tm>f[i]
      then begin
           f[i]:=tm;
           gf[i]:=i-w1[j]; gk[i]:=j
           end;
    end;
   total(n);
 end;


procedure solve2;
  var
     i,j,tm:longint;

 begin
  for i:=0 to n do
    begin
    f[i]:=0; gk[i]:=0;
    end;

   for i:=0 to n do
    for j:=1 to m do
     begin
      if i<w2[j] then continue;
      if w1[j]<=w2[j] then continue;
      tm:=f[i-w2[j]]+w1[j]-w2[j];
      if tm>f[i]
      then begin
           f[i]:=tm;
           gf[i]:=i-w2[j]; gk[i]:=j
           end;
    end;
   total(n);
 end;

procedure print;
 var
     i:longint;
 begin
  writeln(f[N]+N-pn);

  for i:=1 to m do
  if ans[i]=0 then writeln('Buy 0')
              else
                   begin
                     if w1[i]>w2[i]
                     then writeln('Buy ',ans[i],' from Horde')
                     else writeln('Buy ',ans[i],' from Alliance');
                   end;
 end;



begin
  assign(input,'goblin.in');
  assign(output,'goblin.out');
  reset(input); rewrite(output);
  init;
  solve1;
  n:=n+f[N];
  solve2;
  print;
  close(input); close(output);
end.