C++ :

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

int m, n;
int f[100009];

int main() {
	while (cin >> m >> n) {
		if (m == 0 && n == 0) break;
		for (int i = 1; i <= n; i ++) {
			int c, w;
			cin >> c >> w;
			for (int j = m; j >= c; j --) {
				f[j] = max(f[j], f[j - c] + w);
			}
		}
		printf("The most weight is %dg.\n", f[m]);
	}	

	return 0;
}