#include<bits/stdc++.h>
using namespace std;

int main(){
	int dp[1001][1001] = {0},c[1001],w[1001];
	int n,i,j,bw;
	
	cin>>bw>>n;
	for(i = 0;i<n;i++)cin>>w[i]>>c[i];
	
	for(i = 1;i<=n;i++){
		for(j = bw;j>=0;j--){
			if(j>=w[i]){
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-w[i]]+c[i]);
			}
			else dp[i][j] = dp[i-1][j];
		}
	}
	
//	cout<<dp[n-1][bw]<<endl;
	cout<<dp[n][bw]<<endl;
	return 0;
}