#include<bits/stdc++.h>
using namespace std;
long long n,l;
long long dp[1145141],w[1145141],v[1145141];
int main(){
  	cin>>l>>n;
  	for(long long i=1;i<=n;i++){
        cin>>w[i]>>v[i];
    }
  	for(long long i=1;i<=n;i++){
        for(long long j=0;j<=l;j++){
            if(j>=w[i])
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }
  	cout<<dp[l];
  	return 0;
}