#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<stack>
#include<queue>
#include<string>
#include<cstring>
#include<cctype>
#define itn int
#define pritnf printf
#define xlm mylove
#define maxt 1001
#define maxm 110
using namespace std;
int w[maxm],c[maxm];int t,m;int f[maxt][maxm];
inline void readln(){
	freopen("medic.in","r",stdin);
	freopen("medic.out","w",stdout);
	scanf("%d%d",&t,&m);
	for (int i=1;i<=m;i++){
		scanf("%d%d",&w[i],&c[i]);
		//if (w[i]>t){w[i]=c[i]=0;}
	}
}
inline void dp(){
	for (int i=1;i<=m;i++){
		for (int v=t;v>=0;v--){
			if (w[i]<=v) f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
			else f[i][v]=f[i-1][v];
		}
	}
}
inline void p(){
	printf("%d",f[m][t]);
	fclose(stdin);fclose(stdout);
}
int Main(){
	readln();
	dp();
	p();
	return 0;
}
int main(){;}
int xlm=Main();