#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <queue>
#include <stack>

#define sqr(x) (x*x)
#define cube(x) (x*x*x)
#define INF 999999999
#define MOD 100000007

inline bool read(int &x){int c=getchar();int sgn=1;while(~c&&c<'0'||c>'9'){if(c=='-')sgn=-1;c=getchar();}for(x=0;~c&&'0'<=c&&c<='9';c=getchar())x=x*10+c-'0'; x*=sgn; return ~c;}

using namespace std;

struct knapsack {
    int value,weight;
}storage[510];

int k,n,dp_memo[2][2000010];

int main(){
    //freopen("input.txt","r",stdin);

    while(read(k) && read(n)) {
        for (int i=0; i<n; i++) {
            read(storage[i].value);
            read(storage[i].weight);
        }

        int a=0,b=1;
        for (int i=0; i<=n; i++) {
            for (int w=0; w<=k; w++) {
                if (!w || !i)
                    dp_memo[a][w]=0;
                else if (storage[i-1].weight<=w)
                    dp_memo[a][w]=max(dp_memo[b][w-storage[i-1].weight]+storage[i-1].value,dp_memo[b][w]);
                else
                    dp_memo[a][w]=dp_memo[b][w];
            }

            swap(a,b);
        }

        printf("%d\n",dp_memo[n%2][k]);
    }

    return 0;
}