#include<bits/stdc++.h>//万能头
using namespace std;
int n,m;// n背包总容量 m草药个数
int w[105];//储存第i个草药的容量 
int v[105];//储存第i个草药的价值 
int dp[1005];//储存当前容量为i时的最大价值 
int main(){

	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>w[i]>>v[i]; 
	//0-1背包
	for(int i=1;i<=m;i++){//遍历草药 第i个草药 
		for(int j=n;i>=w[i];j--){//遍历背包容量
			dp[j]=max(dp[j],v[i]+dp[j-w[i]]);
		}
	}
	cout<<dp[n];

return 0;
}