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

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

int maxim(int a, int b){
    if (a >=b)
        return a;
    return b;
}

int main(){
    int nr_obiecte;
    int T;
    int G[100];
    int V[100];
    int a[100][100];
    int i, j;
    int p_max = 0;

    fin>>T>>nr_obiecte;
    for (i = 1; i<= nr_obiecte; i++)
        fin >> G[i] >> V[i];

 //   for (i = 1; i<= nr_obiecte; i++)
   //     cout << G[i] <<" "<< V[i]<<endl;

   for(i = 1 ; i <= nr_obiecte ; i++)
    for(j = 1 ; j <= T ; j++)
        if(G[i] == j || a[i-1][j-G[i]] != 0){
            a[i][j] = maxim (a[i-1][j] , a[i-1][j-G[i]] + V[i]);
            p_max = a[i][j];
        }
        else
            a[i][j]=a[i-1][j];


 /*   for(i  = 1; i<= nr_obiecte ; i++){
        for(j = 1 ; j<= T; j++)
            cout<<a[i][j] << " ";
        cout<<endl;
    } */

    fout<<p_max;
    return 0;


}