#include <iostream>
#include <algorithm>
using namespace std;

int main(){
	const int nmax = 100;
	char c;
	int dp[nmax+1][nmax+1];
	int n, w;
	int val[nmax+1], weight[nmax+1];
	while(cin >> w){
		if(w == 0) break;
		cin >> n;
		for(int i = 0; i <= n; i++){
			for(int j = 0; j <= w; j++){
				dp[i][j] = 0;
			}
		}
		for(int i = 1; 1 <= n; i++){
			cin >> val[i] >> c >> weight[i];
		}
		for(int i = 0; i < n; i++){
			for(int j = 0; j <= w; j++){
				if(j < weight[i]){
					dp[i+1][j] = dp[i][j];
				}else{
					dp[i+1][j] = max(dp[i][j], dp[i][j - weight[i]] + val[i]);
				}
			}
		}
		cout << dp[n][w] << endl;
	}
	return 0;
}