记录编号	7576	评测结果	AAAAAAAATA
题目名称	地精贸易	最终得分	90
用户昵称	苏轼	是否通过	未通过
代码语言	Pascal	运行时间	1.179 s
提交时间	2008-11-10 18:01:50	内存使用	4.69 MiB

program cch(input,output);
var
 a,b,c,v,tmp,ans:array[1..100] of longint;
 f,from,ch:array[0..400000] of longint;
 i,n,m,tot,j,n1,l,bc:longint;
begin
 assign(input,'goblin.in');
 assign(output,'goblin.out');
 reset(input);
 rewrite(output);
 readln(n,m);
 bc:=n;
 for i:=1 to m do readln(a[i],b[i]);
 tot:=0;
 for i:=1 to m do
  if a[i]<b[i] then
   begin
    inc(tot);
    c[tot]:=a[i]; v[tot]:=b[i];
    tmp[tot]:=i;
   end;
 for i:=0 to n do f[i]:=-100000;
 f[0]:=0;
 for i:=0 to n do from[i]:=0;
 for i:=1 to m do ans[i]:=0;
 for i:=1 to n do
  for j:=1 to tot do
   if i>=c[j] then
    if f[i]<f[i-c[j]]+v[j] then
     begin
      f[i]:=f[i-c[j]]+v[j];
      from[i]:=i-c[j]; ch[i]:=j;
     end;
 n1:=0;
 for i:=n downto 0 do
   if n1<n-i+f[i] then
    begin
     n1:=n-i+f[i];
     l:=i;
    end;
 i:=l;
 while ch[i]<>0 do
  begin
   inc(ans[tmp[ch[i]]]);
   i:=from[i];
  end;

 tot:=0;
 for i:=1 to m do
  if a[i]>b[i] then
   begin
    inc(tot);
    c[tot]:=b[i]; v[tot]:=a[i];
    tmp[tot]:=i;
   end;
 for i:=1 to n1 do f[i]:=-100000;
 f[0]:=0;
 n:=n1;
 for i:=0 to n do from[i]:=0;
 for i:=0 to n do ch[i]:=0;
 for i:=1 to n do
  for j:=1 to tot do
   if i>=c[j] then
    if f[i]<f[i-c[j]]+v[j] then
     begin
      f[i]:=f[i-c[j]]+v[j];
      from[i]:=i-c[j]; ch[i]:=j;
     end;
 n1:=0;
 for i:=n downto 0 do
   if n1<n-i+f[i] then
    begin
     n1:=n-i+f[i];
     l:=i;
    end;
 i:=l;
 while ch[i]<>0 do
  begin
   inc(ans[tmp[ch[i]]]);
   i:=from[i];
  end;
 writeln(n1-bc);
 for i:=1 to m do
  if ans[i]=0 then writeln('Buy 0')
   else
    if a[i]<b[i] then writeln('Buy ',ans[i],' from Alliance')
     else writeln('Buy ',ans[i],' from Horde');
 close(input);
 close(output);
end.