#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int maxn=1100;
int n,m;
int w[maxn],d[maxn];
int f[maxn][maxn];
int max(int x,int y)
{
	if(x<y)return y;
	else return x;
}
int main()
{
	freopen("medic.in","r",stdin);
	freopen("medic.out","w",stdout);
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>d[i];
	}
	for(int i=1;i<=n;i++)
		for(int j=m;j>0;j--)
		{
			if(w[i]<=j)
			{
				f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+d[i]);
			}
			else{
				f[i][j]=f[i-1][j];
			}
		}
		cout<<f[n][m];
		return 0;
}