#include <iostream>
using namespace std;



int main() {
	int L, n; // L - длина нити  n - количество разных отрезков на которые мы можем делить
	cin >> L >> n;
	int dp[L + 1]; // Массив в котором храним ответ, сколько максимум цены можно набрать для веса i

	memset(dp, 0, sizeof dp); // пока не знаем ответ поэтому максимум можнем набрать 0


	int w[n], c[n]; // длина отрезка i и его цена

	// ввод
	for(int i = 0; i < n; i++) {
		cin >> w[i] >> c[i];
	}

	// рекурентное соотношение
	// для каждого веса i считаем сколько максимум цены можно набрать используя первые j предметов


	for(int i = 0; i < n; i++) {
		for(int j = 0; j <= L; j++) {
			dp[j] = max(dp[j], dp[j - w[i]] + c[i]);
	 	}
	}
	int ans = 0;

	// ищем ответ среди всех весов
	for(int i = 0; i <= L; i++) {
		ans = max(ans, dp[i]);
	}
	cout << ans;
}