RT.我是设 $dp_{i,j}$ 表示前 $i$ 个垃圾，高度为 $j$ 情况下的最高生命值（当前剩余）。
写完之后过了样例感觉没啥问题就交了，结果只有 9 分.......

#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    const int maxn=105;
    int D,G;
    struct Data
    {
        int T,F,H;
    }dt[maxn];
    int dp[maxn][maxn];
    //前 i 个垃圾，堆起来的高度为 j 的最大生命值
    inline bool cmp(Data a,Data b)
    {
        return a.T<b.T;
    }
    void main()
    {
        scanf("%d%d",&D,&G);
        dp[0][0]=10;
        for(int i=1;i<=G;i++)
        {
            scanf("%d%d%d",&dt[i].T,&dt[i].F,&dt[i].H);
        }
        sort(dt+1,dt+G+1,cmp);
        for(int i=1;i<=G;i++)
        {
            for(int j=0;j<=D;j++)
            {
                if(j<dt[i].H)
                {
                    dp[i][j]=dp[i-1][j]+dt[i].F-(dt[i].T-dt[i-1].T);
                    continue;
                }
                dp[i][j]=max(dp[i-1][j]+dt[i].F-(dt[i].T-dt[i-1].T),dp[i-1][j-dt[i].H]-(dt[i].T-dt[i-1].T));
            }
        }
        bool flag=1;
        for(int i=1;i<=G;i++)
        {
            if(dp[i][D]>=0)
            {
                flag=0;
                break;
            }
        }
        if(flag)
        {
            for(int i=1;i<=G+1;i++)
            {
                if(dp[i][0]<0)
                {
                    printf("%d",dp[i-1][0]+dt[i-1].T);
                    break;
                }
            }
        }
        else
        {
            for(int i=1;i<=G;i++)
            {
                if(dp[i][D]>0)
                {
                    printf("%d",dp[i][D]+dt[i].T);
                    break;
                }
            }
        }
    }
}
int main()
{
    Main::main();
    return 0;
}