#include<bits/stdc++.h>
using namespace std;
int f[1005][5],t,m,num,dp[105][105][105];
int dfs(int pos,int sum,int time){
	if(dp[pos][sum][time]){
		return dp[pos][sum][time];
	}
	if(time<0){
		return 1;
	}
	if(pos>m){
		num=max(sum,num);
		return 1;
	}
	dp[pos+1][sum][time]=dfs(pos+1,sum,time);
	dp[pos+1][sum+f[pos][2]][time-f[pos][1]]=dfs(pos+1,sum+f[pos][2],time-f[pos][1]);
}
int main(){
	cin>>t>>m;
	for(int i=1;i<=m;i++){
		cin>>f[i][1]>>f[i][2];
	}
	dfs(1,0,t);
	cout<<num;
	return 0;
}