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

program goblin;
var
  fin,fout:text;
  f,p,pai:array[0..5000000]of longint;
  hash,a,b:array[1..100]of longint;
  n,m:longint;
  i,j:longint;
  max,pp,n0:longint;
begin
  assign(fin,'goblin.in'); reset(fin);
  assign(fout,'goblin.out'); rewrite(fout);
  read(fin,n,m);
  for i:=1 to m do read(fin,a[i],b[i]);
  for i:=1 to m do hash[i]:=0;
  for i:=0 to n do begin
    f[i]:=0;
    p[i]:=0;
    pai[i]:=0;
  end;
  for i:=1 to n do begin
    max:=0;
    for j:=1 to m do begin
      if b[j]<=a[j] then continue;
      if i-a[j]<0 then continue;
      if f[i-a[j]]+b[j]-a[j]>max then begin
        max:=f[i-a[j]]+b[j]-a[j];
        pai[i]:=i-a[j];
        p[i]:=j;
      end;
    end;
    f[i]:=max;
  end;
  pp:=n;
  repeat
    inc(hash[p[pp]]);
    pp:=pai[pp];
  until p[pp]=0;
//*****************************************
  n0:=f[n];
  n:=n0+n;
  for i:=0 to n do begin
    f[i]:=0;
    p[i]:=0;
    pai[i]:=0;
  end;
  for i:=1 to n do begin
    max:=0;
    for j:=1 to m do begin
      if a[j]<=b[j] then continue;
      if i-b[j]<0 then continue;
      if f[i-b[j]]+a[j]-b[j]>max then begin
        max:=f[i-b[j]]+a[j]-b[j];
        pai[i]:=i-b[j];
        p[i]:=j;
      end;
    end;
    f[i]:=max;
  end;
  pp:=n;
  repeat
    inc(hash[p[pp]]);
    pp:=pai[pp];
  until p[pp]=0;
  writeln(fout,f[n]+n0);
  for i:=1 to m do begin
    write(fout,'Buy ');
    write(fout,hash[i]);
    if hash[i]<>0 then begin
      if a[i]<b[i] then begin
        writeln(fout,' from Alliance');
      end;
      if b[i]<a[i] then begin
        writeln(fout,' from Horde');
      end;
    end else writeln(fout);
  end;
  close(fin);
  close(fout);
end.