program dp；
type
arr=array[1..30000] of integer；
var
a,b:array[1..25] of longint；
l:array[1..30000] of integer；
f:array[0..30000] of longint；
n,m,i,link,maxn:longint；
function max(p,q:longint):longint；
begin
if p>q then exit(p)
else exit(q)；
end；
procedure quick(var l:arr；lx,rx:longint)；
var
i,j,x,p:longint；
begin
i:=lx； j:=rx；
x:=l[i+random(j-i)+1]；
repeat
while l[i]<x do inc(i)；
while l[j]>x do dec(j)；
if i<=j then
begin
p:=l[i]； l[i]:=l[j]； l[j]:=p；
inc(i)； dec(j)；
end；
until i>j；
if lx<j then quick(l,lx,j)；
if i<rx then quick(l,i,rx)；
end；
procedure dynamic；
var
i,j,k:longint；
begin
link:=1；
l[1]:=0；
for i:=1 to m do
begin
k:=link；
for j:=link downto 1 do
begin
if l[j]+a[i]<=n then
begin
if f[l[j]+a[i]]=0 then
begin
inc(k)；
l[k]:=l[j]+a[i]；
end；
f[l[j]+a[i]]:=max(f[l[j]+a[i]],f[l[j]]+b[i])；
end；
end；
link:=k；
quick(l,1,link)；
end；
for i:=1 to n do maxn:=max(maxn,f[i])；
write(maxn)；
end；
begin
read(n,m)；
for i:=1 to m do
begin
read(a[i],b[i])；
b[i]:=a[i]*b[i]；
end；
dynamic；
end.
我的DP。。
var
js,n,m,i,j:longint；
d,a,b,c:array[1..25] of longint；
p:array[0..30000] of longint；
begin
read(m)；readln(n)；
for i:=1 to n do begin read(a[i])；read(b[i])；readln；end；
for i:=1 to n do
for j:=m downto a[i] do
begin
if p[j-a[i]]+b[i]*a[i]>=p[j] then p[j]:=p[j-a[i]]+b[i]*a[i]
else p[j]:=p[j]；
end；
write(p[m])；
end.