问题描述

高桥君非常喜欢一款游戏。

这款游戏中有 $N$ 个遗迹，可以按照喜好的顺序进行探索。每个遗迹都有一个从 $1$ 到 $N$ 的编号。

在游戏中可以获得宝石。宝石共有 $M$ 种，编号从 $1$ 到 $M$。

通过探索遗迹可以获得得分和一些宝石奖励。探索遗迹 $i (1 ≤ i ≤ N)$ 可以获得 $s_i$ 分，并获得编号从 $l_i$ 到 $r_i$ 的所有宝石各一个。不能多次探索同一个遗迹。

获得的宝石不能丢弃，如果获得了所有种类的宝石至少一颗，那么会触发魔王复活事件。魔王复活时原本应该获得的得分会消失。

高桥君的目标是尽可能获得高得分，通过选择合适的遗迹探索方式，使得在魔王不复活的情况下获得的得分总和最大。

能够获得的最大得分是多少。

输入

输入以以下格式从标准输入中给出：

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

• 第一行是两个整数 $N (1 ≤ N ≤ 100,000)$ 和 $M (1 ≤ M ≤ 100,000)$，以空格分隔，表示有 $N$ 个遗迹和 $M$ 种宝石。
• 第二行到第 $N$ 行每行包含三个整数 $l_i$, $r_i (1 ≤ l_i ≤ r_i ≤ M)$ 和 $s_i (1 ≤ s_i ≤ 5,000)$，表示探索遗迹 $i (1 ≤ i ≤ N)$ 可以获得 $s_i$ 分，以及获得编号从 $l_i$ 到 $r_i$ 的所有宝石各一个。

配点和部分点

本问题满分为 101 分，其中部分分数可获得。

• 若通过数据集 $1$（满足 $N ≤ 8$ 且 $M ≤ 8$），将获得 $30$ 分。
• 若通过数据集 $2$（满足 $N ≤ 5,000$ 且 $M ≤ 5,000$），将额外获得 $70$ 分。
• 若通过无附加限制的数据集 $3$，将额外获得 $1$ 分。

输出

输出在魔王不复活的情况下，能够获得的最大得分。输出末尾包含换行符。

示例

输入示例1

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

输出示例1

80

例如，按以下顺序探索 $3$ 个遗迹：

• 探索遗迹 $1$。获得 $30$ 分，获得宝石 $1$、$2$ 和 $3$。
• 探索遗迹 $2$。获得 $40$ 分，获得宝石 $2$ 和 $3$。
• 探索遗迹 $4$。获得 $10$ 分，获得宝石 $6$。

最终获得的宝石种类为 $4$ 种（宝石 $1$、$2$、$3$ 和 $6$），魔王不会复活。总得分为 $80$ 分，这是最大值。

输入示例2

2 7
1 3 90
5 7 90

输出示例2

180

探索所有遗迹后，魔王不复活。

输入示例3

1 4
1 4 70

输出示例3

0

无法通过合理的遗迹探索方式阻止魔王复活。