//本次将讨论0/1背包的空间优化问题。
//这是未优化的。显然数组开不大。
#include <stdio.h>
int max(int a,int b)
{
    if(a>b) return a;
    else return b;
}
int main()
{
    int t,m;
    int v[101],c[101],f[101][1001];
    int i,r;
    scanf("%d%d",&t,&m);
    for(i=1;i<=m;i++) scanf("%d%d",&c[i],&v[i]);
    for(r=0;r<=t;r++) if(r<c[1]) f[1][r]=0; else f[1][r]=v[1];
    for(i=2;i<=m;i++)
        for(r=0;r<=t;r++) 
            if(r>=c[i])
                f[i][r]=max(f[i-1][r],f[i-1][r-c[i]]+v[i]);
            else
                f[i][r]=f[i-1][r];
    printf("%d",f[m][t]);
    return 0;
}
/*------------------------华丽丽----------------------------*/
//优化过的。
//事实上f[i][r]一开始用的还是f[i-1][r]的值，因此实际上只需要一个数组。
#include <stdio.h>
int max(int a,int b)
{
	if(a>b) return a;
	else return b;
}
int main()
{
	int t,m;
	int v[101],c[101],f[1001];
	int i,r;
	scanf("%d%d",&t,&m);
	for(i=1;i<=m;i++) scanf("%d%d",&c[i],&v[i]);
	for(r=0;r<=t;r++) if(r<c[1]) f[r]=0; else f[r]=v[1];
	for(i=2;i<=m;i++)
//关键！为保证本次所需要的未用数据不改变，令r递减。
		for(r=t;r>=0;r--) 
			if(r>=c[i])
				f[r]=max(f[r],f[r-c[i]]+v[i]);
			else
				f[r]=f[r];
	printf("%d",f[t]);
	return 0;
}