#include <cmath>
#include <cstring>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int n,m;
int w[N],v[N],dp[205];
int main(){
	cin >> m >> n;
	for(int i=1; i<=n; i++)
	    cin >> w[i] >> v[i];
	for(int i= 1; i<=n; i++){
		for(int j=m; j>=w[i]; j--){
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout << dp[m]; 
	return 0;
}
//01背包0一维数组优解，制作不易，点个赞再走吧