#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int cash,N;
int d[11],n[11];
int dp[100010];
int main()
{
    while(cin>>cash>>N)
    {
        for(int i = 1 ; i <= N ; i++)
        {
            scanf("%d%d",&n[i],&d[i]);
        }
        memset(dp,0,sizeof(dp));
       // int s = 0;
        for(int i = 1; i <= N; i++)
        {
            //cout<<i<<endl;
            for(int k = 1; (k<<1) <= n[i]; k = k<<1)
            {
                //cout<<k<<endl;
                //s++;
                for(int j = cash; j >= 0; j--)
                {
                    dp[j] = dp[j];
                    if(j - k*d[i] >= 0 && dp[j - k*d[i]] + k*d[i] > dp[j])
                    {
                        //cout<<j<<' '<<k<<' '<<d[i]<<endl;
                        dp[j] = dp[j - k*d[i]] + k*d[i];
                    }
                }
                //cout<<i<<' '<<j<<' '<<dp[i][j]<<endl;
            }
        }//cout<<"!!!\n";
        printf("%d\n",dp[cash]);
    }
    return 0;
}