#include<bits/stdc++.h>
using namespace std;
long long dp[1000][1000],w[100],v[100],n,m;
int main(void){
	memset(dp,0,sizeof(dp));
	scanf("%lld %lld",&n,&m);
	for(long long i = 1;i <= m;++i){
		scanf("%lld %lld",&w[i],&v[i]);
	}
	for(long long i = 1;i <= n;++i){
		for(long long j = 1;j <= m;++j){
			if(j >= w[i]) dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]] + v[i]);
			else dp[i][j] = dp[i-1][j];
		}
	}
	printf("%lld",dp[n][m]);
	return 0;
}