//完全背包

 #include<bits/stdc++.h>

 using namespace std;

 const int maxv=;

 const int maxn=;

 int n,m,v[maxn],w[maxn],f[maxv];

 int main()

 {

     scanf("%d%d",&m,&n);

     for(int i=;i<=n;++i) scanf("%d%d",&v[i],&w[i]);

     for(int i=;i<=n;++i)

         for(int j=v[i];j<=m;++j)//从v[i]开始

             f[j]=max(f[j],f[j-v[i]]+w[i]);

     printf("%d",f[m]);

     return ;

 }