#include<bits/stdc++.h>
using namespace std;
int w[1000],c[1000];
int f[100][100];
int max(int x,int y){
    if(x<y) return y;
    else return x;
}
int main(){
    int m,n;
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    cin>>w[i]>>c[i];
    for(int i=1;i<=n;i++)
    for(int v=m;v>0;v--)
    if(w[i]<=v) f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
    else f[i][v]=f[i-1][v];
    cout<<f[n][m];
    return 0;
}