#include <stdio.h>
#include <string.h>

#define MAX_CASH  100002
#define MAX       12

int d[MAX];
int count[MAX];
int used[MAX_CASH];
int cash[MAX_CASH];
int v;

// priority queue
typedef struct {
    int pos;
    int val;
} Entry;
Entry queue[MAX_CASH];
int start, end, window;

static inline
void insert_queue(int val, int pos)
{
    while ( start < end && queue[end-1].val <= val) { end--;}
    queue[end].pos = pos;
    queue[end++].val = val;
    while ((queue[start].pos + window) <= pos) start++;
}

static inline 
int get_max_from_queue()
{
    return queue[start].val;
}

int main()
{
    int n, i, j;

    while (scanf("%d %d", &v, &n) != EOF) {

        for (i = 1; i <= n; i++) {
            scanf("%d %d", &count[i], &d[i]);
        }

        for (i = 0; i <= v; i++) {
            cash[i] = 0;
        }

        for (i = 1; i <= n; i++) {
            // reinit the priority-queue
            int w = d[i];
            start = end = 0;
            window = count[i] + 1;

            // try put
            for (j = 0; j < w; j++) {
                int m, cur = j;
                for (m = 0; cur <= v; m++, cur += w) {
                    // insert cash[cur] - m*w
                    insert_queue(cash[cur] + j - cur, m);
                    // assign it with max + m*w
                    cash[cur] = get_max_from_queue() + cur - j;
                }
            }
        }
        printf("%d\n", cash[v]);
    }
}