#include<bits/stdc++.h>
using namespace std;
int main()
{ 
  int m,n;
  cin>>m>>n;
  int w[n+1];//称重
  int v[n+1];//单个价值
  int f[m+1]={0}; //最大价值
  for(int i=1;i<=n;i++) 
  {
    cin>>w[i]>>v[i];
  }
  for(int i=1;i<=n;i++)
  {
    for(int j=m;j>=w[i];j--)
    {
      f[j]=max(f[j],f[j-w[i]]+v[i]); //判断是否选择i物品
    }
  }
  cout<<f[m];

}