#include <bits/stdc++.h>

using namespace std;

int main() {
	int money = 0, n_items = 0;

	while (cin >> money >> n_items) {
		vector<int> cost(n_items, 0), findex(n_items, 0);
		for (int i = 0; i < n_items; i++)
			cin >> cost[i] >> findex[i];

		money += 200;

		vector<vector<int> > matrix(money + 1, vector<int>(n_items + 1, 0));

		for (int i = 1; i <= money; i++) {
			for (int j = 1; j <= n_items; j++) {
				matrix[i][j] = matrix[i][j - 1];
				if (cost[j - 1] <= i) {
					matrix[i][j] = max(matrix[i][j], findex[j - 1] + matrix[i - cost[j - 1]][j - 1]);
				}
			}
		}

		int bill = 0;
		for (int i = 0; i <= money; i++) {
			if (matrix[i][n_items] == matrix[money][n_items]) {
				bill = i;
				break;
			}
		}
		if (bill > 2000) {
			cout << matrix[money][n_items] << endl;
		}
		else {
			cout << matrix[money - 200][n_items] << endl;
		}
	}
	return 0;
}