#include<iostream>
using namespace std;
int weight[1000001],value[1000001];
int dp[1000001];
int main()
{
	long long num,cap;
	cin >> cap >> num;
	for(int i=1;i<=num;i++)
	{
		cin >> weight[i] >> value[i];
	}
	for(int i=1;i<=num;i++)
	{
		for(int j=1;j<=cap;j++)
		{
			for(int k=0;k*weight[i]<=j;k++)
			{
				if(dp[j-weight[i]*k]+value[i]*k>dp[j])
				{
					dp[j]=dp[j-weight[i]*k]+value[i]*k;
				}
			}
		}
	}
	cout  << dp[cap];
	return 0;
}