#include<bits/stdc++.h>
using namespace std ;
const int maxn = 1000005;
int n,m;
int w[maxn],c[maxn];
int f(int m,int n) {
	if(n==0) return 0;
	int x=f (m,n-1) ;
	int y=0;
	if(m-w[n]>=0) y=f(m-w[n],n-1)+c[n];
	return  max(x,y);
}
int main() {
	cin>>m>>n;
	for(int i=1; i<=n; i++)
		cin>>w[i]>>c[i];
	cout<<f(m,n);
	return 0;
}