#include <iostream>
#include <fstream>
#include <vector>

struct Object
{
	float weight, value;
	
	Object() { weight = 0.0, value = 0.0; }

	Object(float weight, float value)
	{
		this->weight = weight;
		this->value = value;
	}
};

void read(std::vector<Object>& objects, float& maxWeight)
{
	std::ifstream fin("data.in");
	int n;

	fin >> maxWeight;
	fin >> n;
	float weight, value;

	for (int i = 0; i < n; i++)
	{
		fin >> weight >> value;
		objects.push_back({ weight,value });
	}
}

float getMaxValue(const std::vector<Object>& objects,float maxWeight)
{
	std::vector<std::vector<float>> maxValues(objects.size() + 1, std::vector<float>(maxWeight + 1));
	
	for (int i = 0; i <= objects.size(); i++)
		for (int w = 0; w <= maxWeight; w++)
			if (!i || !w)
				maxValues[i][w] = 0;
			else if (w >= objects[i - 1].weight)
				maxValues[i][w] = std::max(objects[i - 1].value + maxValues[i - 1][w - objects[i - 1].weight],
											maxValues[i - 1][w]);
			else
				maxValues[i][w] = maxValues[i - 1][w];

	return maxValues[objects.size()][maxWeight];
}

int main()
{
	float maxWeight;
	std::vector<Object> objects;
	read(objects, maxWeight);
	std::cout << getMaxValue(objects, maxWeight);
}