#include <stdio.h>

 #include <string.h>

 const int N=;

 #define Max(a,b) (a)>(b)?(a):(b)

 int dp[N],cash;

 void ZeroOnePack(int cost)//01背包

 {

     for (int i = cash; i >= cost; i--)

     {

         dp[i] = Max(dp[i],dp[i-cost]+cost);

     }

 }

 void ComplexPack(int cost)//完全背包

 {

     for (int i = cost; i <= cash; i++)

     {

         dp[i] = Max(dp[i],dp[i-cost]+cost);

     }

 }

 void MultiplePack(int cnt,int cost)//多重背包

 {

     if (cnt*cost > cash)

         ComplexPack(cost);

     else

     {

         int k = ;

         while(k < cnt)

         {

             ZeroOnePack(k*cost);

             cnt-=k;

             k<<=;

         }

         ZeroOnePack(cnt*cost);

     }

 }

 int main()

 {

     int n,cost[],cnt[];

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

     {

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

         {

             scanf("%d %d",&cnt[i],&cost[i]);

         }

         memset(dp,,sizeof(dp));

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

         {

             MultiplePack(cnt[i],cost[i]);

         }

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

     }

     return ;

 }