记录编号	850	评测结果	AAAAAAAAAA
题目名称	[NOIP 2006]开心的金明	最终得分	100
用户昵称	EnAsn	是否通过	通过
代码语言	Pascal	运行时间	10.000 s
提交时间	2008-07-22 16:50:19	内存使用	0.00 MiB

program ex;
type
 sz=array [1..25] of integer;
 ss=array [1..30000] of longint;
var
 p,v:sz;
 a:ss;
 m,n:longint;
 f1,f2:text;
procedure init;
 begin
  assign(f1,'happy.in');
  assign(f2,'happy.out');
  reset(f1);
  rewrite(f2);
  readln(f1,n,m);
 end;
procedure main;
 var
  i,j:integer;
 begin
  for i:=1 to m do
   readln(f1,v[i],p[i]);
  for i:=1 to n do a[i]:=0;
  for i:=1 to m do
    for j:=n downto v[i] do
      if (a[j]<a[j-v[i]]+v[i]*p[i]) then
       a[j]:=a[j-v[i]]+v[i]*p[i];
 end;
procedure print;
 begin
  writeln(f2,a[n]);
  close(f1);
  close(f2);
 end;
begin
 init;
 main;
 print;
end.