#include<bits/stdc++.h>
using namespace std;
const int MAX=105;
int T,M,c[MAX],v[MAX],w[MAX];
int main()
{
	cin>>T>>M;
	for(int i=1;i<=M;i++) cin>>w[i]>>c[i];
	for(int i=1;i<=M;i++){
		for(int j=T;j>=w[i];j--){
			v[j]=max(v[j],v[j-w[i]]+c[i]);
		}
	}
	cout<<v[T];
}