const maxn=50010;
type
  xy=record
    t:longint;
    c:string;
  end;
var
  f:array[0..105,0..maxn] of boolean;
  a:array[0..105] of xy;
  s,s1:string;
  n,m,i,j,ans,sum,p,st:longint;
  o:char;

procedure sort(l,r:longint);
var i,j:longint; mid:string[11]; t:xy;
begin
  i:=l; j:=r; mid:=a[(l+r) div 2].c;
  repeat
    while a[i].c<mid do inc(i);
    while a[j].c>mid do dec(j);
    if i<=j then
      begin
        t:=a[i]; a[i]:=a[j]; a[j]:=t;
        inc(i); dec(j);
      end;
  until i>j;
  if l<j then sort(l,j);
  if i<r then sort(i,r);
end;

function clover(st,en:longint):longint;
var i,j,sum,tm:longint;
begin
  f[st-1,0]:=true; sum:=0;
  for i:=st to en do sum:=sum+a[i].t;
  tm:=sum div 2;
  for i:=1 to tm do f[st-1,i]:=false;
  for i:=st to en do
    for j:=0 to tm do
      begin
        if f[i-1,j] then f[i,j]:=true;
        if (j>=a[i].t)and(f[i-1,j-a[i].t]) then f[i,j]:=true;
      end;
  for i:=tm downto 0 do
    if f[en,i] then exit(sum-i);
end;

begin
  //assign(input,'1.in');reset(input);
  readln(m,n);
  while m+n>0 do
    begin
      fillchar(f,sizeof(f),false);
      readln(s);
      for i:=1 to n do readln(a[i].t,o,a[i].c);
      sort(1,n);
      ans:=0; st:=1;
      for i:=1 to n do
        if a[i].c<>a[i+1].c then
          begin
            ans:=ans+clover(st,i);
            st:=i+1;
          end;
      writeln(ans);
      readln(m,n);
    end;
end.