WA了#2，#5，#10点。

#include <bits/stdc++.h>

using namespace std;

struct item {
    int t, f, h;
};

int d, g, dp[101][3001];
item items[101];


inline bool cmp(const item &a, const item &b) {
    return a.t < b.t;
}

int main() {
    scanf("%d%d", &d, &g);
    for(int i = 1; i <= g; i++) {
        scanf("%d%d%d", &items[i].t, &items[i].h, &items[i].f);
    }
    //items[0].h=10;
    sort(items + 1, items + g + 1, cmp);
    int hea = 10;
    int maxt = 10;
    for(int i = 1; i <= g; i++) {
        hea-=(items[i].t - items[i-1].t);
        if(hea < 0) {
            break;
        }
        hea+=items[i].h;
        maxt+=items[i].h;
    }
    for(int i = 0; i <= maxt; i++) {
        dp[0][i]=-0x3ffff;
    }
    dp[0][10]=0;
    for(int i = 1; i <= g; i++) {
        for(int j = maxt; j >= 0; j--) {
            dp[i][j] = -0x3ffff;
            if((j - items[i].h + items[i].t - items[i-1].t) >= 0 && (j - items[i].h + items[i].t - items[i-1].t) <= maxt)
                dp[i][j] = max(dp[i][j], dp[i-1][j - items[i].h + items[i].t - items[i-1].t]);
            if(j+(items[i].t - items[i-1].t) >= 0 && j+(items[i].t - items[i-1].t) <= maxt)
                dp[i][j] = max(dp[i][j], dp[i-1][j+(items[i].t - items[i-1].t)] + items[i].f);
            //if(dp[i][j] >= 0)
            //    printf("dp[%d][%d] = %d\n", i, j, dp[i][j]);
            if(dp[i][j] >= d) {
                printf("%d", items[i].t);
                return 0;
            }
        }
    }
    printf("%d", maxt);
    return 0;
}