#include <cstdio>
#include <cstring>
#define MAX 100005
#define MAXN 11

int m, n, nk, dk, vis[MAXN][MAX], usd[MAXN][MAX];

int main() {
	int i, j, max;
	while(scanf("%d%d", &m, &n) != EOF) {
		memset(vis, 0, sizeof(vis));
		vis[0][0] = 1, max = usd[0][0] = 0;
		for(i = 0; i < n; i++) {
			scanf("%d%d", &nk, &dk);
			for(j = 0; j <= m; j++)
				if(vis[i][j]) {
					if(max < j) max = j;
					vis[i+1][j] = 1, usd[i+1][j] = 0;
					if(j + dk <= m && usd[i][j] < nk && !vis[i][j+dk])
						vis[i][j+dk] = 1, usd[i][j+dk] = usd[i][j] + 1;
				}
		}
		printf("%d\n", max);
	}
	return 0;
}

牛牛们请无视。注意如果加一张当前钞票的数额可以在上一层产生就不要覆盖（记录钞票数量），否则当前钞票不够用。