#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <map>
#include <string>
#include <fstream>


using namespace std;

ifstream in("input.txt");
ofstream out("output.txt");

typedef long long ll;

int main()
{
    int t, n;
    in >> t >> n;
    vector<int> a(t + 1, -1);
    a[0] = 0;
    for (int i = 0; i < n; ++i) {
        int ti, p;
        in >> ti >> p;
        for (int j = t; j > -1; --j) {
            if (a[j] > -1 && j + ti <= t) {
                a[j + ti] = max(a[j + ti], a[j] + p);
            }
        }
    }
    int maxi = 0;
    for (int i = 0; i <= t; ++i) {
        maxi = max(a[i], maxi);
    }
    out << maxi << endl;
    return 0;



}