var v,p,a:array[0..30000] of integer;

i,n,m,q,s,max:longint;

begin

readln(m,n);

for i:=1 to n do readln(v[i],p[i]);

repeat

s:=0;q:=0;

a[n]:=a[n]+1;

for i:=n downto 1 do if a[i]=2 then begin a[i-1]:=a[i-1]+1;a[i]:=0;end;

for i:=1 to n do

if a[i]=1 then begin s:=s+v[i]*p[i];q:=q+v[i];if q>m then break;end;

if (s>max)and(q<=m) then max:=s;

until a[0]=1;

writeln(max);

end.