#include<bits/stdc++.h>

using namespace std;

const int maxn = 105;

int w[maxn] , v[maxn];
int t , m;
long long dp[maxn][maxn];

long long dfs(int i , int j){
	if(i == m) return 0;
	if(dp[i][j] != -1) return dp[i][j]; 
	long long ans = 0;
	if(j >= w[i]){
		ans = max(dfs(i + 1 , j) , dfs(i + 1 , j - w[i]) + v[i]);
	}
	else ans = dfs(i + 1 , j);
	dp[i][j] = ans;
	return ans;
}

int main(){
	memset(dp , -1 , sizeof(dp));
	cin >> t >> m;
	for(int i = 0 ; i < m ; i++){
		cin >> w[i] >> v[i];
	}
	cout << dfs(0 , t) << endl; 
	return 0;
}