← 返回题目列表

AtCoder · past17_h

H. 课程报名

中文机器翻译题面 查看原题

问题陈述

有 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