#include <iostream>
#include <vector>

using namespace std;

int N, K;

typedef struct Task{
    int p, t;
    Task(int p, int t) :p(p), t(t){};
};

int min(int a, int b){ return a < b ? a : b; }

vector<Task*> tasks;
vector<int> start;
vector<int> best;
vector<bool> is;

int f(int t)
{
    if (t > N) return 0;
    else if (is[t]) return best[t];
    else if (start[t] == -1) return f(t + 1);
    else
    {
        int mint = 0x7fffffff;
        for (int i = start[t]; i < K && tasks[i]->p == t; i++)
            mint = min(mint, f(t + tasks[i]->t) + tasks[i]->t);

        best[t] = mint;
        is[t] = true;
        return mint;
    }
}

int main()
{
    freopen("t.txt", "r", stdin);
    cin >> N >> K;
    start.resize(N + 1, -1);
    best.resize(N + 1, 0);
    is.resize(N + 1, false);
    for (int i = 0; i < K; i++)
    {
        int p, t;
        cin >> p >> t;
        tasks.push_back(new Task(p, t));

        if (start[p] == -1)
            start[p] = i;
    }

    cout << N - f(1);

    return 0;
}