Code:

Wa on#5 #10 #12

#include <bits/stdc++.h>
#define int long long
using namespace std;

int d,g,maxt=10;
int dp[110][2510];
bool vis[110][3510];
struct node{
	int t,f,h;
}a[110];

bool cmp(node x,node y){
	return x.t<y.t;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>d>>g;
	for(int i=1;i<=g;i++)
		cin>>a[i].t>>a[i].f>>a[i].h;
	sort(a+1,a+1+g,cmp);
	for(int i=1;i<=g;i++)
		if(maxt>=a[i].t) maxt+=a[i].f;
	memset(dp,-1,sizeof(dp));
	
	dp[0][0]=10;
	vis[0][0]=1;
	for(int i=1;i<=g;i++){
		for(int j=0;j<=2500;j++){
			dp[i][j]=dp[i-1][j]-a[i].t+a[i-1].t;
			if(vis[i-1][j-a[i].h]&&dp[i-1][j-a[i].h]>=a[i].t-a[i-1].t&&j>=a[i].h){
				dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].h]-a[i].t+a[i-1].t);
//				cout<<i<<" "<<j<<endl;
				vis[i][j]=1;
				if(j>=d&&dp[i][j]>=0&&vis[i][j]){
					cout<<a[i].t<<endl;
//					cout<<i<<" "<<j<<endl; 
					return 0;
				}
			}
			if(vis[i-1][j]&&dp[i-1][j]+a[i].f>=a[i].t-a[i-1].t){
				dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i].f-a[i].t+a[i-1].t);
				vis[i][j]=1;
			}
		}
	}
	cout<<maxt;
	return 0;
}