#include<stdio.h>
#include<algorithm>
using namespace std;
#define SIZE 10000005
struct F
{
	long long kal;
	long long money;
};
int main() {

	struct F f[SIZE];
	long long dp[SIZE];
	int V,num;

	scanf("%d%d", &V, &num);
	getchar();

	for (long long i = 0; i < num; i++)
	{
		scanf("%d%d", &f[i].money, &f[i].kal);
	}
	for (long long v = 0;v <= V;v++) {
		dp[v] = 0;
	}
	for (long long  i = 0; i < num; i++)
		for (int v = f[i].money; v <= V; v++)
		{
			dp[v] = max(dp[v], dp[v - f[i].money] + f[i].kal);
		}

	int max = 0;
	for (long long  v = 0;v <= V;v++) {

		if (dp[v]>max)
		{
			max = dp[v];
		}
	}
	printf("%d", max);

	return 0;
}