#include <iostream>
#include<ctime>
#include<map>
#include<vector>
#include<queue>
using namespace std;
long long dp[100005];
int main()
{
   int n;
   int w;
   cin>>w>>n;
   vector<int>weight;
   vector<int>value;
   for(int i=0; i<n; i++){
    int a, b;
    cin>>a>>b;
    value.push_back(a);
    weight.push_back(b);
   }

   for(int i=0; i<=w; i++){
    dp[i]=-1e18;
   }

   dp[w]=0;
   for(int i=w; i>=0; i--){
    for(int j=0; j<n; j++){
        if(i - weight[j] >= 0){
            dp[i-weight[j]]=max(dp[i-weight[j]], dp[i]+value[j]);
        }
        }
   }
   long long result=0;
   for(int j=0; j<=w; j++){
    result=max(result, dp[j]);
   }
   cout<<result;
    return 0;
}