program fish;
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:integer;

procedure dfs(step,mm:integer);
var
  i,j:integer;
  bool:boolean;
  bb1:tb;
begin
  bool:=true;
  for i:=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]);
      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
end;

begin
  assign(input,'fish.in');
  reset(input);
  assign(output,'fish.out');
  rewrite(output);
  readln(m,n);
  for i:=1 to n do
  begin
    readln(r1,r2);
    cost[r1]:=r2;
  end;
  fillchar(b,sizeof(b),0);
  fillchar(s,sizeof(s),0);
  fillchar(bb,sizeof(bb),true);
  readln(r1,r2);
  while (r1>0)and(r2>0) do
  begin
    inc(s[r1]);
    b[r1,s[r1]]:=r2;
    inc(s[r2]);
    b[r2,s[r2]]:=r1;
    readln(r1,r2);
  end;
  dfs(1,m);
  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)
end.