Background

It's for beginners.

Description

一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

Format

Input

共(n+1)行。第一行读入两个整数m，n。
接下来的n行每行读入两个整数，分别为这种物品的质量和价值

Output

One integer,旅行者能获得最大总价值。

Limitation

1s, 1024KiB for each test case.

Hint

program knapsack02;
 const maxm=200;maxn=30;
 type ar=array[1..maxn] of integer;
 var m,n,j,i:integer;
 c,w:ar;
 f:array[0..maxn,0..maxm] of integer;
 function max(x,y:integer):integer;
 begin
  if x>y then max:=x else max:=y;
 end;
 begin
  readln(m,n);
  for i:= 1 to n do
   readln(w[i],c[i]);
  for i:=1 to m do f[0,i]:=0;
  for i:=1 to n do f[i,0]:=0; 

 for i:=1 to n do
   for j:=1 to m do
    begin
      if j>=w[i]  then f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])
     else f[i,j]:=f[i-1,j];
    end;
  writeln(f[n,m]);
  end.