#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll t, m;
    ll f[10000002];

    cin >> t >> m;

    ll a, b;
    for (ll i = 1; i <= m; i++) {
        cin >> a >> b;
        for (ll j = a; j <= t; j++) f[j] = max(f[j], f[j - a] + b);
    }

    cout << f[t];

    return 0;
}

RT