Problem Description

Takahashi loves a certain game.

This game has $ N $ ruins that can be explored in any order. The ruins are numbered from $ 1 $ to $ N $.

There are $ M $ types of gems in the game, numbered from $ 1 $ to $ M $.

Exploring a ruin allows you to earn points and some gems. By exploring ruin $i\ (1\ ≦\ i\ ≦\ N)$, you earn $ s_i $ points and one of each gem numbered from $ l_i $ to $ r_i $. The same ruin cannot be explored multiple times.

Gems cannot be discarded, and if you acquire one or more of every type of gem, an event occurs where the demon king revives. When the demon king revives, the points that should have been earned from the ruin being explored disappear.

Takahashi aims to maximize his score and wants to choose the ruins to explore wisely to maximize the total points earned without the demon king reviving.

What is the maximum possible value?

Input Format

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

$ N $ $ M $ $ l_1 $ $ r_1 $ $ s_1 $ $ l_2 $ $ r_2 $ $ s_2 $ : $ l_N $ $ r_N $ $ s_N $

• The first line contains two integers $N\ (1\ ≦\ N\ ≦\ 100,000)$ and $M\ (1\ ≦\ M\ ≦\ 100,000)$, separated by a space, indicating the number of ruins and the number of types of gems, respectively.
• The next $ N $ lines contain three integers $ l_i $, $r_i\ (1\ ≦\ l_i\ ≦\ r_i\ ≦\ M)$, and $s_i\ (1\ ≦\ s_i\ ≦\ 5,000)$, representing that exploring ruin $i\ (1\ ≦\ i\ ≦\ N)$ earns $ s_i $ points and one of each gem numbered from $ l_i $ to $ r_i $.

Output Format

Output the maximum score that can be obtained without the demon king reviving in one line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

4 6
1 3 30
2 3 40
3 6 25
6 6 10

Sample Output #1

80

Sample Input #2

2 7
1 3 90
5 7 90

Sample Output #2

180

Sample Input #3

1 4
1 4 70

Sample Output #3

0

Notes/Hints

Scoring and Partial Points

This problem is worth $ 101 $ points and has partial scoring.

• If you solve the dataset where $N\ ≦\ 8$ and $M\ ≦\ 8$, you get $ 30 $ points.
• If you solve the dataset where $N\ ≦\ 5,000$ and $M\ ≦\ 5,000$, you get an additional $ 70 $ points.
• If you solve the dataset without additional constraints, you get an additional $ 1 $ point.

Sample Explanation 1

For example, explore three ruins in the following order:
- Explore ruin $ 1 $. Earn $ 30 $ points and gems $ 1, 2, 3 $.
- Explore ruin $ 2 $. Earn $ 40 $ points and gems $ 2, 3 $.
- Explore ruin $ 4 $. Earn $ 10 $ points and gem $ 6 $.

The final types of gems acquired are $ 1, 2, 3, 6 $, so the demon king does not revive. The total score is $ 80 $, which is the maximum.

Sample Explanation 2

Exploring all ruins does not cause the demon king to revive.

Sample Explanation 3

It is not possible to explore the ruins without the demon king reviving.

见题面 Input 部分

见题面 Output 部分