include <bits/stdc++.h>

using namespace std; int m,n,w[1001],c[1001]; //这里是二维数组版本来做0/1背包 int f[1001][1001]; //f[x][y]中，x是物品数量，y是重量。f[x][y]是指在数量为x，重量为y的情况下，最大价值

int main() { cin>>m>>n; for(int i=1; i<=n; i++) {

scanf("%d%d",&w[i],&c[i]);
//输入重量和价值

} for(int i=1; i<=n; i++) {

for(int j=1; j<=m; j++)
{
  //从重量和数量都为一开始枚举，之后不断累积
  if(j>=w[i]) //保证枚举的重量符合条件，不符合就不选，符合才选（所以叫0/1背包）
  {
    f[i][j]=max(f[i-1][j-w[i]]+c[i],f[i-1][j]);//符合的话还要从选和不选再选最大值
  }
  else
  {
    f[i][j]=f[i-1][j];//不符合直接不选，用上一组最大的即可
  }
}

} printf("%d\n\n\n\n\n\n\n\n\n",f[n][m]);//最后输出x=n,y=m的情况，也就是答案 cout<<"你听懂了吗"; return 0; }