#include<bits/stdc++.h>
using namespace std;
int t , m;
int shi[1005];
int value[1005];
int ans = -1e9;
void dp(int x , int sum , int s){
	if(x > m){
		ans = max(ans , sum);
		return ;
	}
	dp(x + 1 , sum , s);
	if(s + shi[x] <= t) dp(x + 1 , sum + value[x] , s + shi[x]);
}
int main(){
	cin >> t >> m;
	for(int i = 1 ; i <= m ; i++){
		cin >> shi[i];
		cin >> value[i];
	}
	dp(1 , 0 , 0);
	cout << ans;
	return 0;
}