#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 m, n;
    while(scanf("%d%d", &m, &n)==2){
        init();
        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]=max(table[i-1][j], j>= price[i]? favour[i]+table[i-1][j-price[i]]:table[i-1][j]);
            }
        }
        printf("%d\n", table[n][m]);
    }


}