#include<iostream>
using namespace std;
int i=0,te=0,tesize,demin,dk[1000001],dp[100001];  
int main(){
    int sumbag,N;
    while(cin>>sumbag>>N)
    { 
    if(sumbag==0||N==0)
    {
             cout<<"0"<<endl; 
             continue; 
    } 
    for(int j=0;j<N;j++)
    {
          cin>>tesize>>demin;
          for(int k=i;k<i+tesize;k++)
          {  
                  dk[k]=demin;
                  te=k;
          } 
     i=te;     
    } 
    for(int j=0;j<=sumbag;j++)
       if(j>=dk[i-1]) dp[j]=dk[i-1];
       else dp[j]=0;     
    for(int j=i-2;j>=0;j--)
           for(int k=0;k<=sumbag;k++)
                 if(k-dk[j]>0&&dp[k]<dp[k-dk[j]]+dk[j]) dp[k]=dp[k-dk[j]]+dk[j];                                                            
    cout<<dp[sumbag]<<endl; 
    }  
    system("pause");
    return 0;
    }