#include<bits/stdc++.h>
using namespace std;
int main(){
	int t,m,vp[10000001],ans,v[10000001],p[10000001];
	cin>>t>>m;
	for(int i=1;i<=m;i++)
		cin>>v[i]>>p[i];
	for(int i=1;i<=m;i++)
		for(int j=v[i];j<=t;j++){
			if(j-v[i]>=0)
				vp[j]=max(vp[j],vp[j-v[i]]+p[i]);	
			else
				vp[j]=vp[j-v[i]];
		}
	cout<<vp[t];
	return 0;
}