记录编号	7624	评测结果	AAAAAAAAAA
题目名称	地精贸易	最终得分	100
用户昵称	辨机ZN	是否通过	通过
代码语言	Pascal	运行时间	2.748 s
提交时间	2008-11-10 20:30:12	内存使用	45.89 MiB

program goblin;
const maxn=4000000;
   var f:array[0..maxn]of longint;
    g:array[-10..maxn,1..2]of longint;
    e,c,d,a,b:array[1..100]of longint;
    f1,f2:text;
    max1,max,n,m,i,j:longint;
procedure deal(t:longint);
begin
  if g[t,1]<>0 then deal(g[t,1]);
  inc(e[g[t,2]]);
end;
procedure print;
var i,k:longint;
begin
   for i:=1 to m do
     if e[i]=0 then writeln(f2,'Buy 0')
       else if c[i]>0 then writeln(f2,'Buy ',e[i],' from Alliance')
         else writeln(f2,'Buy ',e[i],' from Horde');
end;
procedure init;
var i,j:longint;
begin
  assign(f1,'goblin.in');reset(f1);
  assign(f2,'goblin.out');rewrite(f2);
  read(f1,n,m);
  fillchar(c,sizeof(c),0);
  fillchar(d,sizeof(d),0);
  fillchar(e,sizeof(e),0);
  fillchar(f,sizeof(f),0);
  fillchar(g,sizeof(g),0);
  for i:=1 to m do
    begin
      read(f1,a[i],b[i]);
      if a[i]<b[i] then c[i]:=b[i]-a[i];
      if a[i]>b[i] then d[i]:=a[i]-b[i];
    end;
end;
procedure doit;
var i,j,y:longint;
begin
  for i:=1 to m do
    for j:=0 to n do
      if (j-a[i]>=0)and(f[j-a[i]]+c[i]>f[j]) then
      begin
           f[j]:=f[j-a[i]]+c[i];
           g[j,1]:=j-a[i];g[j,2]:=i;
      end;
  max1:=f[n];
  deal(n);
  fillchar(f,sizeof(f),0);
  fillchar(g,sizeof(g),0);
  for i:=1 to m do
    for j:=0 to (max1+n) do
      if (j-b[i]>=0)and(f[j-b[i]]+d[i]>f[j]) then
        begin f[j]:=f[j-b[i]]+d[i];
              g[j,1]:=j-b[i];
              g[j,2]:=i;
        end;
  max:=max1+f[max1+n];
 deal(max1+n);
end;
begin
  init;
  doit;
  writeln(f2,max);
  print;
  close(f1);
  close(f2);
end.