#include <bits/stdc++.h>
using namespace std;
int T,M;
struct beach{
	int num;
	bool f;
}t[105],w[105];
int g[1005];
int dfs(int x){
	if(x<0) return -1e9;
	if(x==0) return 0;
	if(g[x]!=-1e9) return g[x];
	int maxn=INT_MIN;
	for(int i=1; i<=M; i++){
		if(!t[i].f){
			t[i].f=1;w[i].f=1;
			maxn=max(maxn,dfs(x-t[i].num)+w[i].num);
			t[i].f=0;w[i].f=0;
		}
	}
	if(maxn<0) maxn=0;
	return g[x]=maxn;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>T>>M;
	for(int i=1; i<=T; i++){
		g[i]=-1e9;
	}
	for(int i=1; i<=M; i++){
		cin>>t[i].num>>w[i].num;
	}
	cout<<dfs(T)<<"\n";
	return 0;
}