#include<bits/stdc++.h>
using namespace std;
const int N=105;
struct qwq{
	int t,f,h;
}e[N];
bool cmp(qwq x,qwq y){
	return x.t<y.t;
}
int f[N][N];
int d,g;
int main(){
	cin>>d>>g;
	for(int i=1;i<=g;i++)
		cin>>e[i].t>>e[i].f>>e[i].h;
	sort(e+1,e+g+1,cmp);
	memset(f,-0x3f,sizeof(f));
	f[0][0]=10;
	for(int i=1;i<=g;i++){
		for(int j=0;j<=d;j++){
			
			if(f[i-1][j]>=e[i].t)
				f[i][j]=max(f[i][j],
						f[i-1][j]+e[i].f);
			if(j>=e[i].h&&f[i-1][j-e[i].h]>=e[i].t)
				f[i][j]=max(f[i][j],
						f[i-1][j-e[i].h]);
				
		}
	}
	
	int sum=-1e9,ans=-1e9;
	for(int i=1;i<=g;i++){
		for(int j=0;j<=d;j++){
			if(f[i][j]>=e[i].t)
				sum=max(sum,j);
			ans=max(ans,f[i][j]);
		}		
		if(sum==d) break;
	}
	if(sum==d) cout<<e[g].t;
	else cout<<ans;
	return 0;
}

测试点2和10过不去awa，求原因