#include <stdio.h>
#include <string.h>
const int L=100001,M=11;
int cash,n,v[M],c[M],ans;
bool f[L];

int main(void){
    freopen ("1276.in","r",stdin);
    freopen ("1276.out","w",stdout);
    f[0]=true;
    while (scanf ("%d%d",&cash,&n)!=EOF){
          for (int i=1;i<=n;i++)scanf ("%d%d",v+i,c+i);
          if (!n||!cash){printf ("0\n");continue;}
          memset (f+1,false,sizeof (bool)*cash);
          for (int i=1;i<=n;i++){
              int m=v[i];
              for (int j=1;j<=m;m-=j,j<<=1)
                  for (int k=cash;k>=j*c[i];k--)
                      if (f[k-c[i]*j])f[k]=true;
              for (int k=cash;k>=m*c[i];k--)
                      if (f[k-c[i]*m])f[k]=true;
              }
          ans=cash;
          while (!f[ans])ans--;
          printf ("%d\n",ans);
          }
    return 0;
    }