{*******************************************}
{* Program Name:happy                      *}
{* Input file:happy.in                     *}
{* Output file:happy.out                   *}
{* Date:2008.7.22                          *}
{* Programmer:Peng Bo                      *}
{*******************************************}
program happy;
type
  s1=array[1..25]of word;
  s2=array[1..25]of byte;
  s3=Array[1..25,1..10000]of longint;
var
  v:s1;
  w:s2;
  a:s3;
  n:word;
  m:byte;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
function max(a,b:longint):longint;
begin
  if a>b
  then
    max:=a
  else
    max:=b;
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure input;
var
  f:text;
  i:byte;
begin
  assign(f,'happy.in');
  reset(f);
  readln(f,n,m);
  for i:=1 to m do
    readln(f,v[i],w[i]);
  close(f);
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure output;
var
  f:text;
begin
  assign(f,'happy.out');
  rewrite(f);
  write(f,a[m,n]);
  close(f);
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure main;
var
  i:byte;
  j:word;
begin
  for j:=v[1] to n do
    a[1,j]:=w[1]*v[1];
  for i:=2 to m do
    for j:=1 to n do
      if v[i]<=j
      then
        a[i,j]:=max(a[i-1,j],a[i-1,j-v[i]]+v[i]*w[i])
      else
        a[i,j]:=a[i-1,j];
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
procedure cs;
var
  i:word;
begin
  for i:=1 to n do
    a[1,i]:=0;
end;
{~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~}
begin
  input;
  cs;
  main;
  output;
end.
{End}