#include <iostream>using namespace std;int cash, n, m[13], d[13];int f[100100];int money, i, v, temp, k;int solve() { memset(f, 0, sizeof(f)); money = 0; f[0] = 1; for (i=1; i <= n; i++) {  for (v=cash; v >=0; v--) {   if (f[v]) {    for (k=1; k <= m[i]; k++) {     temp = v + k*d[i];     if (temp > cash) break;     if (temp > money) money = temp;     f[temp] = 1;    }   }  } } return money;}int main(){ while (scanf("%d %d", &cash, &n) != EOF) {  for (i=1; i <= n; i++) {   scanf("%d %d", &m[i], &d[i]);  }  printf("%d\n", solve()); } return 0;}