#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int m, n;
int w[N], c[N];
int f[5][N];
int main() {
	int i, j;
	cin >> m >> n;
	for (i = 1; i <= n; i++)
		cin >> w[i] >> c[i];
	for (i = 1; i <= n; i++)
		for (j = 1; j <= m; j++) {
			if (j < w[i])
				f[i & 1][j] = f[(i - 1) & 1][j];
			else f[i & 1][j] = max(f[(i - 1) & 1][j], f[i & 1][j - w[i]] + c[i]);
		}
	cout << f[n & 1][m] << endl;
	return 0;
}