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

#define MAX_N 1500
#define MAX_W 10000

int dp[MAX_N][MAX_W];
int W, N, v[MAX_N], w[MAX_N];

int main() {
	while (true) {
		memset(dp, 0, sizeof(dp));
		cin >> W;
		if (W == 0) { break; }
		cin >> N;
		for (int i = 0; i < N; i++)
		{
			scanf("%d,%d", &v[i], &w[i]);
		}
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j <= W; j++)
			{
				dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);
				if (j + w[i] < W)
				{
					dp[i + 1][j + w[i]] = max(dp[i][j] + v[i], dp[i + 1][j + w[i]]);
				}
			}
		}
		int maxn = 0;
		for (int i = 0; i < MAX_N; i++)
		{
			for (int j = 0; j < MAX_W; j++)
			{
				maxn = max(maxn, dp[i][j]);
			}
		}
		cout << maxn << endl;
	}
}