program l1;

var limit,k,i,t:integer; a:array[0..25]of longint;w:array[0..25]of integer;

f:array[0..25,0..30000]of longint;

function max(c,b:longint):longint;

begin

if c>b then max:=c else max:=b;

end;

begin

readln(limit,k);

for i:=1 to k do

begin

readln(a[i],t);

w[i]:=a[i]*t;

end;

for i:=1 to k do f[i,0]:=0;

for i:=1 to limit do f[0,i]:=0;

for i:=1 to k do

for t:=limit downto 1 do

if a[i]<=t then f[i,t]:=max(f[i-1,t-a[i]]+w[i],f[i-1,t])

else f[i,t]:=f[i-1,t];

writeln(f[k,limit]);

end.

w:array[0..25]of integer; 应该为 w:array[0..25]of longint;