O(nm)每件物品只能买一次，s是每件物品的总和，方程是:f[j]:=max(f[j],f[j-a[i]]+s[i]);var n,m,i,j:longint; a,b,s,f:array[0..30000] of longint;begin readln(n,m); for i:=1 to m do begin readln(a[i],b[i]); s[i]:=a[i]*b[i]; end; for i:=1 to m do for j:=n downto a[i] do if f[j-a[i]]+s[i]>f[j] then f[j]:=f[j-a[i]]+s[i]; writeln(f[n]);end.
