Problem Description

A primary school has a very long corridor. It extends east-west, from the west end to the east end, covering $ L $ meters. Due to the school's policy, there are no windows, so the corridor must be illuminated by fluorescent lights.

There are $ N $ fluorescent lights in the corridor. The $ i $th fluorescent light can illuminate the area between $ l_i $ meters and $ r_i $ meters from the west end. Additionally, the cost to turn on each fluorescent light varies. It costs $ c_i $ yen to turn on the $ i $th fluorescent light.

While turning on all the fluorescent lights would make the entire corridor bright, the school is short on funds and wants to illuminate the entire corridor with the least possible cost. Determine the minimum cost required to ensure that every point in the corridor, i.e., between $ 0 $ meters and $ L $ meters from the west end, is illuminated by at least one fluorescent light.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains the number of fluorescent lights $N\ (1\ ≦\ N\ ≦\ 10^5)$ and the length of the corridor $L\ (1\ ≦\ L\ ≦\ 10^5)$, separated by spaces.
• The next $ N $ lines, where the $ i $th line contains integers representing the range illuminated by the $ i $th fluorescent light $l_i,\ r_i\ (0\ ≦\ l_i\ ＜\ r_i\ ≦\ L)$ and the cost to turn it on $c_i\ (1\ ≦\ c_i\ ≦\ 10^5)$, separated by spaces.
• It is guaranteed that turning on all fluorescent lights will illuminate the entire corridor.

Output Format

Output the minimum cost required to illuminate the entire corridor in one line.

Sample Input and Output

Sample Input #1

5 5
0 1 1
1 2 1
2 4 3
3 5 1
2 3 2

Sample Output #1

5

Sample Input #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

Sample Output #2

1080

Sample Input #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

Sample Output #3

6

Sample Input #4

5 5
0 1 100000
1 2 100000
2 3 100000
3 4 100000
4 5 100000

Sample Output #4

500000

Notes/Hints

Partial Points

This problem has partial scoring:

• $ 60 $ points are awarded for correctly solving the dataset where $1\ ≦\ N\ ≦\ 3,000\ ,1\ ≦\ L\ ≦\ 3,000$.
• An additional $ 40 $ points are awarded for correctly solving the dataset where $1\ ≦\ N\ ≦\ 10^5\ ,1\ ≦\ L\ ≦\ 10^5$. The total score is $ 100 $ points.

Sample Explanation 1

Turning on the $1,\ 2,\ 4,\ 5$th fluorescent lights results in the minimum total cost.

Sample Explanation 2

Unless the $ 6 $th fluorescent light is turned on, the area between $ 7 $ meters and $ 8 $ meters from the west end will not be illuminated. Using only the $ 6 $th fluorescent light is the optimal solution.

见题面 Input 部分

见题面 Output 部分