#include <stdio.h>
#include <string.h>

long long max(long long x1,long long x2)
{
	return x1>x2?x1:x2; 
}
int bag(int weight,int n,int *w,int *v)
{
	int i,j;
	long long f[n+1][weight+1];
	memset(f,0,sizeof(int)*(n+1)*(weight+1));//初始条件、边界状态
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=weight;j++)//迭代公式 
		{
			//当动态背包容量小于第i个物品的重量时
			//表示在该动态背包容量下不装入第i个物品对应的最大价值 
			f[i][j]=f[i-1][j];
			//当动态背包容量大于第i个物品的重量时 
			//可以选择装入或不装入
			//不装入第i个物品，即该动态背包容量第i-1个物品对应的最大价值
			//装入第i个物品，即第i个物品的价值加上动态背包剩余容量对应的第i-1个物品的最大价值
			if(j>=w[i])
				f[i][j]=max(f[i][j],f[i][j-w[i]]+v[i]);
		}
	}
	return f[n][weight];
}
int main()
{
	int i,j,weight,n,max;
	scanf("%d %d",&weight,&n);//输入背包容量和物品个数 
	int w[n+1],v[n+1];
	for(i=1;i<=n;i++)//输入物品的重量和价值 
		scanf("%d %d",&w[i],&v[i]);
	max=bag(weight,n,w,v);
	printf("%lld",max);
	return 0;
}