問題文
一所小学有一条很长的走廊。从东向西延伸,从西端延伸到东端 L 有米。 由于学校政策,根本没有窗户,所以走廊必须用荧光灯照明。
在这个走廊里 它有 N 荧光灯。 i 第一个荧光灯来自西端。 l_i 计点和 r_i 可以在米之间照明。 此外,打开不同荧光灯所需的成本也不同。 打开第 i 个荧光灯 c_i 费用为日元。
可以通过打开所有荧光灯来照亮整个走廊,但由于我没有钱,所以我想以尽可能小的成本照亮整个走廊。 从西端开始,在走廊的哪一点? 0 计点和 L 求打开荧光灯所需的最低成本,以便以米为单位的点之间的每个点都被至少一个荧光灯照亮。
入力
输入将以以下形式通过标准输入给出。
N L l_1 r_1 c_1 l_2 r_2 c_2 : l_N r_N c_N
约束中的描述不充分,因此已更正。 “荧光灯照射范围”→“表示荧光灯照射范围的整数”(21:20)
- 1 第一行是一个整数,表示荧光灯的数量。 N (1 ≦ N ≦ 10^5) 和一个代表走廊长度的整数 一个整数,表示第L(1 ≦ L ≦ 10^5)用空格分隔。
- 2 来自行 N 行数过多 i 在线i个荧光灯照射的范围 l_i, r_i (0 ≦ l_i < r_i ≦ L) 以及开启它的成本 c_i (1 ≦ c_i ≦ 10^5) 用空格分隔。
- 打开所有荧光灯保证照亮整个走廊。
部分点
针对此问题设置了部分分数。 如果正确答案是满足
- 1 ≦ N ≦ 3,000 ,1 ≦ L ≦ 3,000的数据集 如果正确答案是满足 60 分被给予。
- 1 ≦ N ≦ 10^5 ,1 ≦ L ≦ 10^5的数据集,则进一步 给出 40 点。总共100点。
出力
打印一行照亮整个走廊所需的最低成本。 当第
入力例1
5 5 0 1 1 1 2 1 2 4 3 3 5 1 2 3 2
出力例1
5
1, 2, 4, 5个荧光灯打开时,总成本最小化。 从西端出发,除非你打开第
入力例2
8 10 0 2 1 2 3 1 0 4 1 0 2 1 3 7 1 0 10 1080 8 10 1 9 10 1
出力例2
1080
6号荧光灯。7计点和8仪表点之间的距离不会被照亮。 最好的打开方式是仅使用第 6个荧光灯。
入力例3
10 10 0 1 1 1 2 1 2 3 1 3 4 1 4 5 1 0 5 4 5 7 2 6 8 3 8 10 1 2 9 3
出力例3
6
入力例4
5 5 0 1 100000 1 2 100000 2 3 100000 3 4 100000 4 5 100000
出力例4
500000