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

program fish;
uses sysutils;
type
  tb=array[0..31] of boolean;
var
  ans,a,cost,s:array[0..31] of integer;
  b:array[0..31,0..31] of integer;
  bb:tb;
  i,j,n,m,max,maxm,r1,r2,zong,ss:integer;
  tt:real;

procedure print;
begin
  if max>0 then
  begin
    writeln(max,' ',m-maxm);
    for i:=1 to max do
      writeln(ans[i]);
  end
  else
    writeln('0 0');
  close(input);
  close(output);
  halt
end;

procedure dfs(step,mm,last:integer);
var
  i,j:integer;
  bool:boolean;
  bb1:tb;
begin
  bool:=true;
  for i:=last+1 to n do
    if (bb[i]) and (cost[i]<=mm) then
    begin
      a[step]:=i;
      bool:=false;
      bb1:=bb;
      bb[i]:=false;
      for j:=1 to s[i] do
        bb[b[i,j]]:=false;
      dfs(step+1,mm-cost[i],i);
      bb:=bb1;
    end;
  if bool then
  begin
    if (step-1>max)or((step-1=max)and(mm<maxm)) then
    begin
      max:=step-1;
      maxm:=mm;
      ans:=a;
    end;
  end;
  if (now*86400)-tt>0.9
    then print;
end;

begin
  assign(input,'fish.in');
  reset(input);
  assign(output,'fish.out');
  rewrite(output);
  tt:=now*86400;
  readln(m,n);
  for i:=1 to n do
  begin
    readln(r1,r2);
    cost[r1]:=r2;
    zong:=zong+r2;
  end;
  fillchar(b,sizeof(b),0);
  fillchar(s,sizeof(s),0);
  fillchar(bb,sizeof(bb),true);
  readln(r1,r2);
  ss:=0;
  while (r1>0)and(r2>0) do
  begin
    inc(ss);
    inc(s[r1]);
    b[r1,s[r1]]:=r2;
    inc(s[r2]);
    b[r2,s[r2]]:=r1;
    readln(r1,r2);
  end;
  if (zong<=m) and (ss=0) then
  begin
    writeln(n,' ',zong);
    for i:=1 to n do
      writeln(i);
    close(input);
    close(output);
    halt
  end;
  dfs(1,m,0);
  print;
end.