```cpp
var i,j,k,n,m:longint;
x,b,c,y:array[0..1000]of longint;
begin
read(m,n);
for i:=1 to n do
read(b[i],c[i]);
for i:=1 to n do
begin
y:=x;
for j:=1 to m do
if j<b[i] then
x[j]:=y[j]
else
if y[j-b[i]]+c[i]>y[j]then
x[j]:=y[j-b[i]]+c[i]
else
x[j]:=y[j];
end;
write(x[m]);
end.
```
by 温鑫 @ 2015-06-20 08:54:02