记录编号	27651	评测结果	AAAAAAAAAA
题目名称	垃圾陷阱	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2011-09-29 07:49:14	内存使用	0.26 MiB

#include <cstdio>
#include <cstdlib>
struct gab {
    int t, f, h;
} a[102];
inline int cmp(const void *x, const void *y) {
    gab *u, *v;
    u = (gab *)x;
    v = (gab *)y;
    return u->t - v->t;
}
int d, g, f[102];
bool found;
int main() {
    freopen("well.in","r",stdin);
    freopen("well.out","w",stdout);
    scanf("%d %d", &d, &g);
    for(int i=0; i<g; i++)
        scanf("%d %d %d", &a[i].t, &a[i].f, &a[i].h);
    qsort(a, g, sizeof(a[0]), cmp);
    f[0] = 10;
    for(int i=0; i<g; i++) {
        found = false;
        for(int j=d; j>=0; j--) {
            if(f[j] >= a[i].t) {
                if(j + a[i].h >= d) {
                    printf("%d\n", a[i].t);
                    goto end;
                }
                if(f[j] > f[j+a[i].h])
                    f[j+a[i].h] = f[j];
                f[j] += a[i].f;
                found = true;
            }
        }
        if(!found)
            break;
    }
    printf("%d\n", f[0]);
end:
    return 0;
}