#include <bits/stdc++.h>
using namespace std;
pair<int,int>g[201];
int n,m,ans;
void dfs(int dep,int w,int c);
int main() {
	scanf("%d%d",&m,&n);
	for(int i = 1;i<=n;i++)scanf("%d%d",&g[i].first,&g[i].second);
	dfs(1,0,0);
	printf("%d",ans);
	return 0;
}
void dfs(int dep,int w,int c){
	if(w>m)return;
	if(dep>n){
		if(!w && !c)return;
		ans = max(ans,c);
		return;
	}
	dfs(dep+1,w,c);
	dfs(dep+1,w+g[dep].first,c+g[dep].second);
}