#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N*10],w[N],v[N];

int main()
{
    int n,m;
    cin>>m>>n;
    memset(f,0,sizeof f);

    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]);

    cout<<f[m];
}