记录编号	14450	评测结果	AAAAAAAAAA
题目名称	地精贸易	最终得分	100
用户昵称	打不死的羊	是否通过	通过
代码语言	Pascal	运行时间	0.504 s
提交时间	2009-10-29 20:24:12	内存使用	32.54 MiB

program goblin;
type
fxz1=array[1..100] of longint;
fxz3=array[0..2000000] of longint;
fxz4=array[0..2000000] of boolean;
var
f1,f2:text;
i,j,n,m,ls,max,nn:longint;
l,b,p:fxz1;
q,d:fxz3;
ans,ans3:fxz3;
flag:fxz4;

begin assign(f1,'goblin.in');
      assign(f2,'goblin.out');
      reset(f1);rewrite(f2);
      readln(f1,n,m);nn:=n;
      for i:=1 to m do
      begin readln(f1,l[i],b[i]);
            p[i]:=b[i]-l[i];
      end;
      for i:=1 to n do ans3[i]:=0;
      flag[0]:=true;
      for i:=1 to m do
      if p[i]>0 then  for j:=0 to n do
                      if (flag[j])and(ans[j+l[i]]<ans[j]+p[i])and(j+l[i]<=n)
                       then begin ans[j+l[i]]:=ans[j]+p[i];
                                  q[j+l[i]]:=j;
                                  d[j+l[i]]:=i;
                                  flag[j+l[i]]:=true;
                             end;
      max:=0;
      for i:=1 to n do if max<=ans[i] then begin max:=ans[i];ls:=i;end;
      n:=max+n;
      while ls<>0 do begin inc(ans3[d[ls]]);ls:=q[ls];end;

      for i:=0 to n do begin flag[i]:=false;
                             ans[i]:=0;
                             q[i]:=0;d[i]:=0;
                       end;
      flag[0]:=true;
      for i:=1 to m do p[i]:=-p[i];
      for i:=1 to m do
      if p[i]>0 then  for j:=0 to n do
                      if (flag[j])and(ans[j+b[i]]<ans[j]+p[i])and(j+b[i]<=n)
                       then begin ans[j+b[i]]:=ans[j]+p[i];
                                  q[j+b[i]]:=j;
                                  d[j+b[i]]:=i;
                                  flag[j+b[i]]:=true;
                             end;
      max:=0;
      for i:=1 to n do if max<=ans[i] then begin max:=ans[i];ls:=i;end;
      n:=n+max;
      while ls<>0 do begin dec(ans3[d[ls]]);ls:=q[ls];end;
      n:=n-nn;
      writeln(f2,n);
      for i:=1 to m do
      begin write(f2,'Buy ',abs(ans3[i]));
            if ans3[i]>0 then write(f2,' from Alliance');
            if ans3[i]<0 then write(f2,' from Horde');
            writeln(f2);
      end;
      close(f1);close(f2);
end.