#include<bits/stdc++.h>
using namespace std;
long long a[100],b[100],c,n,m;
void dfs(long long q,long long x,long long y,long long o){//q为容量//x为价值//y为当前//o为选择 
	if(y==m)
		return;
	if(q-a[y]<0&&x>c&&o==1){
		c=x;
		dfs(q,x,y+1,1);
		dfs(q,x,y+1,0);
	} 
	else
		if(o==1){
			dfs(q-a[y],x+b[y],y+1,1);
			dfs(q-a[y],x+b[y],y+1,0);
		}else{
			dfs(q,x,y+1,1);
			dfs(q,x,y+1,0);
		}
		return;
}
int main(){
	//freopen("knapsack.in","r",stdin);
	//freopen("knapsack.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>a[i]>>b[i];
	dfs(n,0,1,0);
    dfs(n,0,1,1);
	cout<<c;
	return 0;
}