#include<stdio.h>
#define max(a,b)	(a>b?a:b)
int n,m;
int f[100000];
int main()
{
	scanf("%d %d",&m,&n);
	for(int i=1;i<=n;i++)
	{
		int w,v;
		scanf("%d %d",&w,&v);
		for(int j=m;j>=w;j--)
		f[j]=max(f[j],f[j-w]+v);
	}
	printf("%d",f[m]);
	return 0;
}
/**************************************************************
	Problem: 1282
	User: admin
	Language: C
	Result: Accepted
	Time:50 ms
	Memory:1536 kb
****************************************************************/