AT_arc026_3.[ARC026C] 蛍光灯

某小学有一条非常长的走廊，东西方向延伸，从西端到东端的长度为 $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$
$\vdots$
$l_N$ $r_N$ $c_N$

• 第 $1$ 行包含两个整数，$N$ 表示荧光灯的数量（$1 \leq N \leq 10^5$），$L$ 表示走廊的长度（$1 \leq L \leq 10^5$）。
• 接下来的 $N$ 行中，第 $i$ 行包含三个整数，分别为第 $i$ 盏荧光灯照亮的区间 $l_i, r_i$（$0 \leq l_i < r_i \leq L$），以及点亮该灯所需的费用 $c_i$（$1 \leq c_i \leq 10^5$）。
• 保证如果点亮所有荧光灯，走廊整体一定可以被照亮。

请输出照亮整个走廊所需的最小费用。

部分分

本题设置了部分分。

• 若能正确解决 $1 \leq N \leq 3,000,\ 1 \leq L \leq 3,000$ 的数据集，可获得 $60$ 分。
• 若能正确解决 $1 \leq N \leq 10^5,\ 1 \leq L \leq 10^5$ 的数据集，可再获得 $40$ 分，总计 $100$ 分。

样例解释 1

当点亮第 $1, 2, 4, 5$ 盏荧光灯时，费用总和最小。

样例解释 2

如果不点亮第 $6$ 盏荧光灯，西端第 $7$ 米到第 $8$ 米之间的区域无法被照亮。只使用第 $6$ 盏荧光灯是最优的点亮方式。

由 ChatGPT 4.1 翻译