#BS0028. [HTOI-2] 送外卖

[HTOI-2] 送外卖

题目背景

外卖公司董事长小B 压榨员工 让外卖员小A送一个宇宙超级无敌紧急的单子!

题目描述

NN 个单子要送,小A必须在 TT 时刻或之前全部送完,其中送第 ii 个订单需要花 aia_i 分钟送,规定送达时刻为第 bib_i 分钟,送达得到收入为 cic_i 元。订单 ii 若不晚于 bib_i 分钟送达,小A可以获得全额收入,否则不能获得收入。

小A必须分别送这些单子。

你知道,小A的OI不好,因此他请来了机房里最强大的强袭暗灭勋章鱼人守卫来帮他计算能获得的最大收入是多少。但不幸的是,ta不在,所以只好由你来解决了!

输入格式

第一行两个正整数 NNTT

之后 NN 行,每行三个整数 aia_ibib_icic_i

输出格式

输出小A能获得的最大收入。

样例 #1

样例输入 #1

5 12
4 9 9
3 4 7
5 2 12
3 12 2
5 7 8

样例输出 #1

19

提示

对于 20%20\% 的数据,N8N \le 8

对于 100%100\% 的数据,N5000N \le 50001biT1041 \le b_i \le T \le 10^41ai,ci10001 \le a_i,c_i \le 1000