#include <bits/stdc++.h>
using namespace std;
int times[10000001],value[10000001],p[10000001];
int main() {
	int t,m,n1 = 0; 		//能够用来采药的时间 t 和代表山洞里的草药的数目m
	scanf("%d%d", &t,&m);
	for(int i = 1; i <= m; i++) {
		int x,y,num = 1;
		scanf("%d%d", &x,&y);
		int s = t/x;
		while(s >= num) {
			times[++n1] = x*num;
			value[n1] = y*num;
			s-=num;
			num *= 2;
		}
		times[++n1] = x*s;
		value[n1] = y*s;
	}
	for(int i = 1; i <= n1; i++) {
		for(int j = t; j >= times[i]; j--) {
			if(p[j-times[i]]+value[i] > p[j]) p[j] = p[j-times[i]]+value[i];
		}
	}
	printf("%d", p[t]);
	return 0;
}