#include<iostream>
#include<cstring>
using namespace std;
int main(){
	int dp[1001], w, v, T, M;
	cin >> T >> M;
	memset(dp, 0, sizeof(dp));
	for(int i=1; i<=M; i++){
		cin >> w >> v;
		for(int j=T; j>=w; j--)
			dp[j] = max(dp[j-w]+v, dp[j]);
	}
	cout << dp[T];
}