#include <iostream>
#include <fstream>
using namespace std;

ifstream in("rucsac.in");
ofstream out("rucsac.out");

const int MAX_NR=5001;
const int MAX_G=10001;
int obiecte,greutate;
int wt[MAX_NR],val[MAX_NR];
int dp[MAX_G+1];

int maxim(int a,int b){
    return(a>b ? a:b);
}

void citire(){
    in>>greutate>>obiecte;
    for(int i=1;i<=obiecte;i++){
        int a,b;
        in>>a>>b;
        wt[i]=a;
        val[i]=b;
    }
}

void sol(){
    for(int i=1;i<=obiecte;i++){
        for(int j=greutate;j>=wt[i];j--){
            dp[j]=maxim(dp[j],val[i]+dp[j-wt[i]]);
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);
    out.tie(NULL);
    citire();
    sol();
    out<<dp[obiecte];
}