#include <iostream>
#include <vector>
using namespace std;
int main(){
	int t,m;
	cin>>t>>m;
	vector<vector<long long>>dp(m+1,vector<long long>(t+1,0));
	for(int i=1;i<=m;++i){
		int cost,value;
		cin>>cost>>value;
		for(int j=0;j<=t;++j){
			dp[i][j]=dp[i-1][j];
			for(int k=1;k*cost<=j;++k){
				dp[i][j]==max(dp[i][j],dp[i-1][j-k*cost]+k*value);
			}
		}
	}
	cout<<dp[m][t]<<endl;
	return 0;
}