#include <iostream>
#include <string.h>
#include <iomanip>
#include <algorithm>
using namespace std;

struct a{
	int va;
	int ti;
}l[10001];


long long t,m;
long long mem[10001][1001];//用的记忆化搜索

int cmp(a aa,a bb){
	return aa.ti>bb.ti;
}

int fi(int rest,int lin){
	if(mem[rest][lin]!=-1) return mem[rest][lin];
	else{
		if(lin==m+1) return 0;
		
		if(rest-l[lin].ti>=0) return mem[rest][lin]=max(fi(rest,lin+1),max(fi(rest-l[lin].ti,lin)+l[lin].va,fi(rest-l[lin].ti,lin+1)+l[lin].va));
		
		else return mem[rest][lin]=fi(rest,lin+1);
	}
}

int main(){
	memset(mem,-1,sizeof(mem));
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>l[i].ti>>l[i].va;
	}
	sort(l+1,l+1+m,cmp);
	cout<<fi(t,1);
	return 0;
}