#include <iostream>
using namespace std;



int main() {
	int L, n;
	cin >> L >> n;
	int dp[L + 1];
	memset(dp, 0, sizeof dp);
	int w[n], c[n];
	for(int i = 0; i < n; i++) {
		cin >> w[i] >> c[i];
	}
	for(int i = 0; i <= L; i++) {
		for(int j = 0; j < n; j++) {
			if(w[j] <= i) dp[i] = max(dp[i], dp[i - w[j]] + c[j]);
		}
	}
	int ans = 0;
	for(int i = 0; i <= L; i++) {
		ans = max(ans, dp[i]);
	}
	cout << ans;
}