#include<bits/stdc++.h>

using namespace std;

int tt,m,t[101001],c[101001],f[101001];

int main()
{
	scanf("%d%d",&tt,&m);
	for(int i=1;i<=m;++i)
		scanf("%d%d",&t[i],&c[i]);
	for(int i=1;i<=m;++i)
		for(int j=tt;j>=0;--j)
			f[j]=max(f[j],f[j-t[i]]+c[i]);
	printf("%d",f[tt]);
	
	return 0;
}

本地测试了第一个和第二个测试点都能过，然而提交后是全WA