C++ :

#include <bits/stdc++.h>
using namespace std;

int m, n;
int w[105], c[105], f[1010];

int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i ++) cin >> w[i] >> c[i];
		
	for (int i = 1; i <= n; i ++) {
		for (int j = m; j >= w[i]; j --) {
			f[j] = max(f[j], f[j-w[i]] + c[i]);
		}
	}
	
	cout << f[m] << endl;

	return 0;
}