#include<bits/stdc++.h>
using namespace std;
int d,g;
struct ku{
	int t=0,h=0,f=0;
}trash[110];
int dp[150][150];
bool cmp(ku x,ku y){
	return x.t<y.t;
}
int main(){
	cin>>d>>g;
	for(int i=1;i<=g;i++) cin>>trash[i].t>>trash[i].f>>trash[i].h;
	memset(dp,-1,sizeof(dp));
	dp[0][0]=10;
	sort(trash+1,trash+g+1,cmp);
	for(int i=1;i<=g;i++){
		int t=trash[i].t,h=trash[i].h,f=trash[i].f;
		for(int j=0;j<=d+25;j++){
		//	printf("\ni:%dj:%d-",i,j);
			if(t>dp[i-1][j]+trash[i-1].t) continue;
			int pastt=(t-trash[i-1].t);
			if(j>=h)
				dp[i][j]=max(dp[i-1][j-h],dp[i-1][j]+f-pastt);
			else
				dp[i][j]=dp[i-1][j]+f-pastt;
	//		printf("%d ",dp[i][j]);
		}
	}
	int ans=-1;
	for(int i=1;i<=g;i++){
		for(int j=d;j<=d+25;j++){
			if(dp[i][j]>=0){
				ans=trash[i].t;
				break;
			}
		}
	}
	if(ans!=-1) printf("%d",ans);
	else printf("%d",dp[g][0]);
	return 0;
	
}