#include <iostream>
#include <stdio.h>
using namespace std;

bool neng[100005];
int zx[100005];
int zxgs[100005];

int main() {
	int tot;
	while(scanf("%d", &tot) > 0){
		if(tot < 0) return 0;
		int gs;
		scanf("%d", &gs);
		if(gs == 0){
			printf("%d\n", 0);
			continue;
		}
		int zs[12], mz[12];
		int GS = 0;
		for(int i = 1; i <= gs; i++){
			int tempzs, tempmz;
			scanf("%d%d", &tempzs, &tempmz);
			if(tempzs == 0) continue;
			zs[GS+1] = tempzs;
			mz[GS+1] = tempmz;
			GS++;
		}
		gs = GS;
		//printf("%d\n", gs);
		neng[0] = 1;
		zx[0] = 0;
		zxgs[0] = 0;
		for(int i = 1; i <= tot; i++) neng[i] = 0;
		for(int i = 1; i <= gs; i++){
			for(int j = 0; j <= tot; j++){
				if(neng[j] || j < mz[i] || !neng[j-mz[i]]) continue;
				int sc = j - mz[i];
				if(zx[sc] < i){
					neng[j] = 1;
					zx[j] = i;
					zxgs[j] = 1;
				}
				else if(zxgs[sc] < zs[i]){
					neng[j] = 1;
					zx[j] = i;
					zxgs[j] = zxgs[sc] + 1;
				}
			}
		}

		for(int i = tot; i >= 0; i--){
			if(neng[i]){
				printf("%d\n", i);
				break;
			}
		}
	}
	return 0;
}