记录编号	16180	评测结果	AAAAAAAA
题目名称	王伯买鱼	最终得分	100
用户昵称	reamb	是否通过	通过
代码语言	Pascal	运行时间	3.219 s
提交时间	2010-04-21 17:27:33	内存使用	0.24 MiB

uses sysutils;
var
  d,i,j,n,m,l,s,t,r,p,zhonglei,min,min1,max1:integer;
  time:real;
  w:boolean;
  biaozhi:array[0..40] of boolean;
  jilu,q,a:array[0..40] of integer;
  guanxi:array[0..40,0..40] of boolean;
procedure sousuo (k:integer);
var
  z:integer;
begin
  if now*86400-time>0.95 then
  begin
    writeln (zhonglei,' ',d-min);
    for i:=1 to zhonglei do
      writeln (jilu[i]);
  close (input);
  close (output);
  halt
  end;
  for z:=1 to n do
  begin
    w:=true;
    for l:=1 to k-1 do
      if guanxi[q[l],z]=false then
        w:=false;
    if (z>q[k-1]) and (biaozhi[z]=true)
    and (m-a[z]>=0) and (w=true)
    and (m div min1+k>zhonglei)then
    begin
      q[k]:=z;
      biaozhi[z]:=false;
      m:=m-a[z];
      if k>zhonglei then
      begin
        zhonglei:=k;
        min:=m;
        for l:=1 to k do
          jilu[l]:=q[l]
      end
      else
        if k=zhonglei then
        begin
          if m<min then
          begin
            min:=m;
            for l:=1 to k do
              jilu[l]:=q[l]
          end
        end;
      sousuo(k+1);
      biaozhi[z]:=true;
      m:=m+a[z]
    end
  end
end;
begin
  assign (input,'fish.in');
  reset (input);
  assign (output,'fish.out');
  rewrite (output);
    readln (m,n);
    d:=m;
    min:=m;
    for i:=0 to n do
      for j:=0 to n do
        guanxi[i,j]:=true;
    for i:=1 to n do
      biaozhi[i]:=true;
    max1:=0;
    min1:=maxint;
    for i:=1 to n do
    begin
      readln (s,t);
      if t<min1 then
        min1:=t;
      if t>max1 then
        max1:=t;
      a[s]:=t
    end;
    q[0]:=0;
    readln (p,r);
    while (p<>0)and(r<>0) do
    begin
      guanxi[p,r]:=false;
      guanxi[r,p]:=false;
      readln (p,r)
    end;
    time:=now*86400;
    sousuo(1);
    writeln (zhonglei,' ',d-min);
    for i:=1 to zhonglei do
      writeln (jilu[i]);
  close (input);
  close (output)
end.