#include <iostream>
#include <stdio.h>
using namespace std;
int a[100][3],b,c,d,l,m,s,t=10,r=0,k[100][2100];
bool bo[100][3000]={false},boo;
int main(void)
{
	freopen ("well.in","r",stdin);
	freopen ("well.out","w",stdout);
	scanf("%d%d",&b,&c);
	for (d=0;d<c;d++) scanf("%d%d%d",&a[d][0],&a[d][1],&a[d][2]);
	r=0;
	for (d=0;d<c;d++)
	{
		r=a[d][0];
		boo=false;
		if (d==0)
		{
			k[d][t+a[d][1]]=0;
			k[d][t]=a[d][2];
			if (r<=t) 
			{
				boo=true;
				bo[d][t+a[d][1]]=true;
			}
			if (r<=t)
			{
				boo=true;
				bo[d][t]=true;
			}
			if (boo==false) break;
		}
			else 
			{
				for (l=10;l<2100;l++)
					if (bo[d-1][l]==true)
					{
						k[d][l+a[d][1]]+=k[d-1][l];
						if (r<=l) 
						{
							boo=true;
							bo[d][l+a[d][1]]=true;
						}
							else bo[d][l+a[d][1]]=false;
						m=k[d-1][l]+a[d][2];
						if (m>k[d][l]) k[d][l]=m;
						if (r<=l) 
						{
							boo=true;
							bo[d][l]=true;
						}
							else bo[d][l+a[d][1]]=false;
					}
				if (bo==false) break;
			}
	}
	if (d==c)
	{
		s=101;
		for (d=0;d<100;d++)
			for (l=0;l<2100;l++)
				if (bo[d][l]==true)
					if ((k[d][l]>=b)&&(d<s)) s=d;
		printf("%d",a[s][0]);
	}
		else 
		{
			s=10;
			for (d=0;d<100;d++)
			{
				t+=a[d][0];
				if (t>s) break;
				s+=a[d][1];
			}
			printf("%d",s);
		}
	fclose(stdin);
	fclose(stdout);
	return 0;
}