#include<iostream>
#include<cstdio>

using namespace std;

typedef long long ll;
ll i,j,k;
ll w[100000],v[100000];
ll f[10000000];
ll n,m;

int main(){
	scanf("%lld%lld",&m,&n);
	for(i=1;i<=n;i++){
		scanf("%lld%lld",&w[i],&v[i]);
	}
	for(i=1;i<=n;i++){
		for(j=w[i];j<=m;j++){
			f[j]=max(f[j-w[i]]+v[i],f[j]);
		}
	}
	printf("%lld",f[m]);
	return 0;
}