问题陈述
有 N 大学课程。 i- 第门课程需要努力 a_i,预定于 b_i第一个时隙,并计数 c_i 学分。
您需要参加一些课程才能获得总共 M 积分。但是,您不能在同一时间段选修多门课程。
如果你能赚到 M 或更多学分,打印这样做所需的最小总努力;否则,打印 -1.
约束
- 1 \leq N, M \leq 5000
- 1 \leq a_i,b_i,c_i \leq 5000
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 c_1 \vdots a_N b_N c_N
输出
如果你能赚到 M 或更多学分,打印这样做所需的最小总努力;否则,打印 -1.
示例输入 1
3 4 3 1 2 4 1 2 5 2 2
示例输出 1
8
如果您采取 1-st 和 3-rd课程,所需的总努力是 8,这是最小值。
请注意,您不能同时使用 1-st 和 2-nd 课程,因为它们被安排在同一时段。
示例输入 2
3 100 1 100 1 1 200 1 1 300 1
示例输出 2
-1
即使你修完了所有课程,你也无法赚取 100 或更多学分。
示例输入 3
2 100 10 5 99 10 5 99
示例输出 3
-1
两门课程安排在同一时间段,因此您无法赚取 100 或更多学分。
示例输入 4
10 522 4575 1426 4445 3772 81 3447 629 3497 2202 2775 4325 3982 4784 3417 2156 1932 902 728 3537 3857 739 1918 4211 4679 3506 3340 1568 1868 16 2940
示例输出 4
629