//Accepted    1100 KB    47 ms
 //多重背包
 #include <cstdio>
 #include <cstring>
 #include <iostream>
 #include <queue>
 #include <cmath>
 #include <algorithm>
 using namespace std;
 /**
   * This is a documentation comment block
   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！
   * @authr songt
   */
 ;
 ;
 int dp[imax_v];
 int weight[imax_n],amount[imax_n];
 int n,v;
 int max(int a,int b)
 {
     return a>b?a:b;
 }
 void zeroOnePack(int weight,int value,int v)
 {
     for (int j=v;j>=weight;j--)
     dp[j]=max(dp[j],dp[j-weight]+value);
 }
 void completePack(int weight,int value,int v)
 {
     for (int j=weight;j<=v;j++)
     dp[j]=max(dp[j],dp[j-weight]+value);
 }
 void multiplePack(int weight,int value,int amount,int v)
 {
     ;
     if (amount*weight>=v)
     {
         completePack(weight,value,v);
         return ;
     }
     while (k<amount)
     {
         zeroOnePack(k*weight,k*value,v);
         amount-=k;
         k<<=;
     }
     zeroOnePack(amount*weight,amount*value,v);
 }
 void Dp()
 {
     ;i<=v;i++) dp[i]=;
     ;i<=n;i++)
     {
         multiplePack(weight[i],weight[i],amount[i],v);
     }
     ;
     ;i<=v;i++)
     ans=max(ans,dp[i]);
     printf("%d\n",ans);
 }
 int main()
 {
     while (scanf("%d%d",&v,&n)!=EOF)
     {
         ;i<=n;i++)
         scanf("%d%d",&amount[i],&weight[i]);
         Dp();
     }
     ;
 }