#include <iostream>
#define MAX 100005
using namespace std;

int v[20000];
int dp[100005];

int main()
{
   int cash,n,i,j,cnt,k,m;
   dp[0] = 1;
   while(scanf("%d%d",&cash,&n) != EOF)
   {
       if(!n || !cash)  {   printf("0\n");  continue;}
        cnt = 0;
        for(i = 0;i < n;i++)
        {
            scanf("%d%d",&k,&m);
            int ccnt = cnt;
            for(j = cnt ;j < ccnt + k;cnt++,j++)    v[j] = m;
        }
        memset(dp + 1,0,sizeof(int) * cash);
        for(i = 0;i < cnt;i++)
            for(j = cash;j >= 0;j--)
                if(dp[j] && !dp[j + v[i]])
                    dp[j + v[i]] = 1;
        int ans = cash;
        while(!dp[ans]) ans--;
        printf("%d\n",ans);
    }
    return 0;
}