rt

#include<bits/stdc++.h>
using namespace std;
#define int long
int f[11451400]={0},v[11451400]={0},a[11451400]={0};
#undef int
int main(){
    #define int long
    int t,m;
    cin>>t>>m;
    for(int i=0;i<=m;)cin>>a[i]>>v[i++];
    for(int i=1;i<=m;i++){
        for(int j=a[i];j<=t;j++){
            f[j]=max(f[j],f[j-a[i]]+v[i]);
        }
    }
    cout<<f[t];
}