//1342. 开心的金明

 #include <iostream>

 using namespace std;

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

 int backpack(int w[], int v[], int n, int c)

 {

     //w表示重要度

     //v表示价格

     //c表示价格总量

     int max[n+][c+];

     for (int j = ; j <= c; j++)

     {

         if (j<v[]) max[][j] = ;

         else max[][j] = w[]*v[];

     }

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

     {

         for (int j = ; j <= c; j++)

         {

             if (j < v[i]) max[i][j] = max[i-][j];

             else max[i][j] = MAX(max[i-][j], (max[i-][j-v[i]]+v[i]*w[i]));

         }

     }

     return max[n][c];

 }

 int main()

 {

     int c, n;

     while (cin>>c>>n)

     {

         int w[n+], v[n+];

         for (int i = ; i <= n; i++) cin>>v[i]>>w[i];

         cout<<backpack(w,v,n,c)<<endl;

     }

     return ;

 }