问题文

某小学校有一条非常长的走廊。它从东到西延伸，长度为 $L$ 米。根据学校的政策，走廊没有窗户，因此必须用荧光灯照明走廊。

走廊上有 $N$ 盏荧光灯。第 $i$ 盏荧光灯可以照亮离西端 $l_i$ 米到 $r_i$ 米之间的区域。另外，每盏荧光灯照亮所需的费用不同。点亮第 $i$ 盏荧光灯需要花费 $c_i$ 元。

虽然可以点亮所有荧光灯来照亮整个走廊，但由于资金有限，希望以尽可能少的费用来照亮整个走廊。请计算出在保证走廊上的每个地点（即从西端到东端之间的每个地点）至少被一盏荧光灯照亮的情况下，所需的最小费用。

---

输入

输入通过标准输入给出，具体格式如下：

$N$ $L$ $l_1$ $r_1$ $c_1$ $l_2$ $r_2$ $c_2$ : $l_N$ $r_N$ $c_N$

由于约束条件的描述不完整，已进行修正："蛍光灯の照らす範囲" → "蛍光灯の照らす範囲を表す整数"（21:20）

• 第 $1$ 行是两个整数 $N$ 和 $L$，分别表示荧光灯的数量 $(1 \leq N \leq 10^5)$ 和走廊的长度 $L (1 \leq L \leq 10^5)$。
• 第 $2$ 行到第 $N$ 行，每行包含一个整数 $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

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

---