#include <bits/stdc++.h>

using namespace std;

int main()
{
int m,n;
cin>>m>>n;
vector <int> f,c,w;
f.resize(m+1);
c.resize(n+1);
w.resize(n+1);
int i,j;
for(i=1;i<=n;++i)
cin>>w[i]>>c[i];
for(i=0;i<=m;++i)
f[i]=0;
for(i=0;i<=n;++i)
for(j=m;j>=w[i];--j)
f[j]=max(f[j],w[i]*c[i]+f[j-w[i]]);
cout<<f[m];
return 0;
}

水
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long int i,j,n,m,u[300001],v[300001],map[300001],s=0,scan1,scan2;
void init ()
{
scanf ("%lld%lld",&m,&n);
for (i=1;i<=n;i++) {
scanf ("%lld%lld",&scan1,&scan2);
if (scan1<=m) {
s++;
u[s]=scan1;
v[s]=scan2;
}
}
memset (map,0,sizeof (map));
}
int max (int x,int y)
{
if (x>=y) return x;
else return y;
}
void work ()
{
for (i=1;i<=s;i++) {
for (j=m;j>=u[i];j--) {
map[j]=max(map[j-u[i]]+v[i]*u[i],map[j]);
}
}
}
void output ()
{
printf ("%d",map[m]);
}
int main ()
{
//freopen ("happy.in","r",stdin);
//freopen ("happy.out","w",stdout);
init ();
work ();
output ();
//system ("pause");
//fclose (stdin);
//fclose (stdout);
return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long f[320000];
long long w[320000];
long long c[320000];
int max(int a,int b)
{
return a>b?a:b;
}
int n,m,i,j,x,y;
int main ()
{
freopen ("happy.in","r",stdin);
freopen ("happy.out","w",stdout);
scanf ("%d%d",&m,&n);
for (i=1;i<=n;i++)
{
scanf ("%d%d",&x,&y);
w[i]=x*y*1LL;
c[i]=x*1LL;
}
memset (f,0,sizeof(f));
for (i=1;i<=n;i++)
{
if (c[i]>m) continue;
for (j=m;j>=c[i];j--)
{
f[j]=max(f[j],f[j-c[i]]+w[i]);
}
}
printf ("%ld",f[m]);
fclose (stdin);
fclose (stdout);
}