#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <sstream>
#define rep(i, a, n) for(int i = a;i < n;i++)
using namespace std;


using P = pair<bool, int>;


int W, N;
int tv[1010];
int tw[1010];


void input(){
	string s;
	stringstream ss;
	cin >> N;
	rep(i, 0, N){
		cin >> s;
		replace(s.begin(), s.end(), ',', ' ');
		ss.clear();
		ss << s;
		ss >> tv[i] >> tw[i];
	}
}


int search(int i, int w){
	if(i == N) return 0;
	if(tw[i] <= w) return max(search(i+1, w-tw[i]) + tv[i], search(i+1, w));
	else if(tw[i] > w) return search(i+1, w);
	return 0;
}


int main(){
	int d = 0;
	while(d++, cin >> W, W){
		input();
		cout << search(0, W) << endl;
	}

	return 0;
}