#include<bits/stdc++.h>
using namespace std;
const int N=11000;
int a[N];
int w[N];
int f[N][N];

bool digit(char x)
{
    return (x>='0' && x<='9');
}
inline int read()
{
	int x=0;
	int f=1;
	char ch=getchar();
	while(!digit(ch))
	{
		if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(digit(ch))
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

int main()
{
	int T;
	T=read();
	int n;
	n=read();
	for(int i=1;i<=n;i++)
	{
		a[i]=read();
		w[i]=read();
	}
	int ans=-1;
	for(int i=1;i<=n;i++)
	{
		for(int j=T;j>=a[i];j--)
		{
			f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+w[i]);
			ans=max(f[i][j],ans);
		}
	}
	cout<<ans;
	return 0;
}