program wangbomaiyu;
var
  d,i,j,n,m,l,s,t,r,p,zhonglei,min:integer;
  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
  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 (w=true) and (biaozhi[z]=true)
    and (m-a[z]>0) 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;
    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;
    for i:=1 to n do
    begin
      readln (s,t);
      a[s]:=t
    end;
    readln (p,r);
    while (p<>0)and(r<>0) do
    begin
      guanxi[p,r]:=false;
      guanxi[r,p]:=false;
      readln (p,r)
    end;
    sousuo(1);
    writeln (zhonglei,' ',d-min);
    for i:=1 to zhonglei do
      writeln (jilu[i]);
  close (input);
  close (output)
end.