题目描述

强哥很喜欢玩某个游戏。 这个游戏有$N$个遗迹，编号从$1到N$，可以按照喜欢的顺序探索。

在游戏中可以获得宝石共$有M种，从1到M$编号。通过探索遗迹可以获得得分和一些宝石作为报酬。探索遗迹$i（1 ≤ i ≤ N）$可以获得得分$S_i$分，同时获得编号为$L_i$到$R_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$

输出格式

一个整数表示答案

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

80

按照以下顺序探索三个遗迹。

探索遗迹1。得分为30分，获得宝石1、宝石2和宝石3。

探索遗迹2。得分为40分，获得宝石2和宝石3。

探索遗迹4。得分为10分，获得宝石6。

最终获得的宝石种类有宝石1、宝石2、宝石3和宝石6共4种，魔王不会复活。合计得分为80分。 对于20%的数据 $1<=N,M<=8$

对于50%的数据 $1<=N,M<=5000$

对于100%的数据$1<=N,M<=100000,\ 1<=L_i<=R_i<=M,\ 1<=S_i<=5000$