/*
s[i]表示i能否取到，然后不断更新s即可，如果用个队列维护待更新的节点速度应该会更快
*/
#include <iostream>
const int MAXN = 100010;
int s[MAXN], st[MAXN], inq[MAXN];
int main(){
	int t, n;
	while (scanf("%d%d",&t,&n))
	{
		int k, num;
		memset(s, 0, sizeof(s)); 
		memset(inq, 0, sizeof(inq));
		s[0] = true;
		for (int i = 0; i < n; ++i){
			scanf("%d%d",&k,&num);
			memset(st, 0, sizeof(st));
			for (int i = 0; i <= k; ++i){
				for (int j = t - num * i; j >= 0; --j){
					if (s[j]) st[j + num * i] = true;
				}
			}
			memcpy(s, st, sizeof(s));
		}
		for (int p = t; p >= 0; --p){
			if (s[p])
			{
				printf("%d\n",p); 
				break;
			}
		}
	}
	return 0;
}