#include<bits/stdc++.h>
const double dT=0.9762;
const int SIZE=150;
using namespace std;
int V,m,t[SIZE],w[SIZE],timn;//限制的时间，种类，用时数组，价值数组，总时间。
int dE,ans,tot,vis[SIZE];//能量变化，答案，总价值，是否访问的数组。
double T=2000;//初温

bool accept(int dE)
{
	return ((dE>0)||exp(dE/T)>(double)rand()/RAND_MAX);
}

int main()
{
	cin>>V>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>t[i]>>w[i];
	}
	
	while(T>1e-14)
	{
		ans = ans < tot ? tot : ans;
		int a=rand()%m+1;
		int dE=w[a];
		if(vis[a]) dE*=-1;
		if(accept(dE))
		{
			if(vis[a])
			{
				vis[a]=0;
				tot-=w[a];
				timn-=t[a];
			}
			else
			{
				if(t[a]+timn>V) continue;
				vis[a]=1;
				tot+=w[a];
				timn+=t[a];
			}
		}
		T*=dT;
	}
	cout<<ans<<endl;
	return 0; 
}