var n,m:longint;

v,p,f:array[0..30003]of longint;

i,j,ans:longint;

//function max(a,b:longint):longint;

// begin

// if a>b then exit(a) else exit(b);

// end;

begin

readln(n,m);

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

for i:=1 to n do

for j:=n downto v[i] do

begin

ans:=f[j-v[i]]+v[i]*p[i];

if f[j]<ans then f[j]:=ans;

// f[j]:=max(f[j],f[j-v[i]]+v[i]*p[i]);

end;

writeln(f[n]);

end.

超了四个 怎么办 ....