#include<iostream>
#include<cstdio>
using namespace std;

int sum_time, n, time1[105], money[105], dp[105][1005];	//dp[i][j]表示前i件在j时间内最多可以得到多少价值 

int dfs(int n, int sum_time){
	if(n == 0)	return 0;
	if(sum_time <= 0)	return 0;
	if(sum_time-time1[n] < 0)	return dp[n-1][sum_time];
	if(dp[n-1][sum_time] == 0)	dp[n-1][sum_time] = dfs(n-1, sum_time);
	if(dp[n-1][sum_time-time1[n]] == 0)	dp[n-1][sum_time-time1[n]] = dfs(n-1, sum_time-time1[n]);
	return max(dp[n-1][sum_time], dp[n-1][sum_time-time1[n]]+money[n]);
}

int main(){
	cin>> sum_time>> n;
	for(int i=1; i<=n; i++){
		cin>> time1[i]>> money[i];
	}
	cout<< dfs(n, sum_time);
	return 0;
}