#include <iostream>
#include <string.h>
using namespace std;
int f[1000005];
int main()
{
int sum, n, C;
int num[11], v[11];
int max;
while(scanf("%d", &sum) != EOF)
{
scanf("%d", &n);
int i, inc, j, newc;
for(i = 0; i < n; i ++)
scanf("%d %d", &num[i], &v[i]);
max = 0;
f[0] = 1;
C = sum;
for(i = 0; i < n; i ++)
{
inc = 1;
//if(num[i] > C / v[i]) num[i] = C / v[i];
while(num[i] > 0)
{
if(inc > num[i]) inc = num[i];
num[i] = num[i] - inc;
for(j = C; j >= v[i] * inc; j --)
{
if(!f[j])
{
f[j] = f[j - v[i] * inc];
}
if(f[j] && max < j) max = j;
}
inc = inc << 1;
}
}
for(i = 1; i <= max; i ++) f[i] = 0;
printf("%d\n",max);
}
}