#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int cash,N;

int v[],n[],dp[],t[];

int main()

{

    while(~scanf("%d%d",&cash,&N))

    {

        int cnt = ;

        for(int i=;i<=N;i++)

        {

            scanf("%d%d",&n[i],&v[i]);

            if(n[i] == ||v[i] == ) continue;

            int k = ;

            while(n[i]-k>)

            {

                t[cnt++] = k*v[i];

                n[i]-=k;

                k<<=;

            }

            if(n[i]) t[cnt++] = v[i]*n[i];

        }

        memset(dp,,sizeof dp);

        for(int i=;i<cnt;i++)

        {

            for(int j=cash;j>=t[i];j--)

            {

                dp[j] = max(dp[j],dp[j-t[i]]+t[i]);

            }

        }

        printf("%d\n",dp[cash]);

    }

}
//听队友说睡前适合做dp~