program fish;
var
  m,n,i,j,p,t1,t2,ansm,ansn:integer;
  f:array[1..30,1..2]of integer;
  tab:array[1..30,1..30]of integer;
  hx,hx2:array[1..30]of integer;
procedure find(x,y:integer);
var
  i:integer;
begin
  if (x>ansn)or((x=ansn)and(y>ansm)) then begin
    ansn:=x;
    ansm:=y;
    hx2:=hx;
  end;
  for i:=1 to n do
  begin
    if (x<n)and(y+f[i,2]<=m) then begin
      p:=0;
      for j:=1 to n do
        if (tab[f[i,1],j]=1)and(hx[j]=1) then begin
          p:=1;
          break;
        end;
      if (p=0)and(hx[f[i,1]]=0)and(x<n) then begin
        hx[f[i,1]]:=1;
        find(x+1,y+f[i,2]);
        hx[f[i,1]]:=0;
      end;
    end;
  end;
end;
begin
  ansm:=0;
  ansn:=0;
  fillchar(tab,sizeof(tab),0);
  fillchar(hx,sizeof(hx),0);
  assign(input,'fish.in');
  assign(output,'fish.out');
  reset(input);
  rewrite(output);
  readln(m,n);
  for i:=1 to n do
    readln(f[i,1],f[i,2]);
  readln(t1,t2);
  while (t1<>0)and(t2<>0) do
  begin
    tab[t1,t2]:=1;
    tab[t2,t1]:=1;
    readln(t1,t2);
  end;
  find(0,0);
  writeln(ansn,' ',ansm);
  for i:=1 to n do
    if hx2[i]=1 then writeln(i);
  close(input);
  close(output);
end.