#include <bits/stdc++.h>
#define L(i, m, n) for(int i(m);i < n;i++)
#define pb push_back
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define in(x) cin >> x
#define SZ(X) int(X.size())
#define clr(A, V) L(i, 0, 111) A[i]=V
#define ff first
#define ss second
#define RF(X) freopen(X, "r", stdin)
#define WF(X) freopen(X, "w", stdout)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef pair<int, string> pis;
typedef vector<string> vs;
typedef pair<pair<int, int>, pair<int, int > > piiii;

int table[109][10009], price[109], favour[109];
void init(){
    memset(table, 0, sizeof(table));
    memset(price, 0, sizeof(price));
    memset(favour, 0, sizeof(favour));
}
int main(){
//    WF("out.txt");
    int cnt=0;
    int m, n;
    while(scanf("%d%d", &m, &n)==2){
        init();
        m+=200;

        L(i,1,n+1)in(price[i]), in(favour[i]);

        for(int i=0;i<=n;i++) table[i][0]=0; for(int j=0;j<=m;j++)if(j>=price[0])table[0][j]=favour[0];/**Base**/

        for(int i = 1;i<=n;i++){
            for(int j = 1;j<=m;j++){
                table[i][j]=table[i-1][j];
                if(j>= price[i])
                    table[i][j]=max(table[i][j], favour[i]+table[i-1][j-price[i]]);
            }
        }
        int cost =0, x=n, y=m;
        while(x>0&&y>0){
            if(table[x][y]!=table[x-1][y])
                cost+=price[x], y-=price[x];
            x--;
        }
        if(cost>2000)
            cout << table[n][m] <<endl;
        else
            cout << table[n][m-200]<<endl;

    }


}