/*********************************************************************
    程序名:
    版权: 归作者所有
    作者: 洛谷:ca0vnv
    日期: 2024-05-04 19:49
    说明: 这里应该没有村里人了吧
*********************************************************************/
#include <bits/stdc++.h>
using namespace std;
int m, n, p[9005], t[9005], dp[100005];

signed main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		cin >> p[i] >> t[i];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = t[i]; j <= m; j++) {
			dp[j] = max(dp[j], dp[j - t[i]] + p[i]);
		}
	}
	cout << dp[m];
	return 0;
}