#include <bits/stdc++.h>
using namespace std;
int d,g,t[105],f[105],h[105],cntf[105],cnth[105],seqt[105],mxtime=10;
int dp[105][205];
bool marked[105][205];
bool compt(int a,int b) {
	return t[a]<t[b];
}
int main() {
	//freopen("well1.in","r",stdin);
	scanf("%d%d",&d,&g);
	for (int i=1;i<=g;i++) {
		scanf("%d%d%d",&t[i],&f[i],&h[i]);
		seqt[i]=i;
	}
	sort(seqt+1,seqt+g+1,compt);
	for (int i=0;i<=g;i++) {
		mxtime+=f[seqt[i]];
		if (mxtime<t[seqt[i+1]]) break;
	}
	cntf[0]=10;
	for (int i=1;i<=g;i++) {
		cntf[i]=cntf[i-1]+f[seqt[i]];
	}
	//printf("%d",mxtime);
	bool can=0;
	dp[0][0]=10;
	marked[0][0]=1;
	for (int i=1;i<=g;i++) {
		int pos=seqt[i];
		for (int j=d;j>=0;j--) {
			if (marked[i-1][j]) {
				if (dp[i-1][j]+f[pos]+t[seqt[i-1]]-t[pos]>=0) {
					dp[i][j]=max(dp[i][j],dp[i-1][j]+f[pos]+t[seqt[i-1]]-t[pos]);
					marked[i][j]=1;
				}
				if (dp[i-1][j]+t[seqt[i-1]]-t[pos]>=0){
					if (j+h[pos]>=d) {
						printf("%d",t[pos]);
						can=1;
						break;
					}
					else {
						dp[i][j+h[pos]]=dp[i-1][j]+t[seqt[i-1]]-t[pos];
						marked[i][j+h[pos]]=1;
					}
				}
			}
			//printf("%d %d %d\n",i,j,dp[i][j]);
		}
		if (can) break;
		//printf("%d ",pos);
	}
	if (!can) printf("%d",mxtime);
}

输入数据：

42 25
10 25 1
10 25 1
10 25 1
10 25 1
10 25 1
10 25 1
10 25 1
10 25 1
10 25 1
10 25 1
10 26 5
10 26 5
10 26 5
10 26 6
10 25 1
10 25 1
10 25 1
10 25 1
10 25 1
10 25 1
10 25 1
10 25 1
10 25 1
10 25 1
510 1 21

应该输出 $510$，该代码输出 $615$