問題文
高桥喜欢某种游戏。
这个游戏有 这里有 N 遗迹,你可以按照你喜欢的顺序探索它们。废墟中 它们的编号最大为 1 到 N 。
游戏过程中可以获得宝石。宝石是 M 有不同的类型, 编号至1 到 M 。
通过探索遗迹,可以获得积分和一些宝石作为奖励。废墟 通过搜索得分 i (1 ≦ i ≦ N) 通过探索赚取积分 s_i 赚取积分及数量 l_i 以上 r_i 以下所有宝石 1 一一获取。你不能多次探索同一个废墟。
获得的宝石无法丢弃,所有类型的宝石都无法丢弃。 1 如果你获得超过一个,就会发生魔王复活的事件。当恶魔领主复活时,他在探索遗迹中获得的积分将会消失。
高桥的目标是获得尽可能高的分数,通过选择遗迹进行探索,他希望在魔王复活的情况下获得最大的总分数。
最大可能值是多少?
入力
输入将以以下形式从标准输入给出。
N M l_1 r_1 s_1 l_2 r_2 s_2 : l_N r_N s_N
- 1 行中,2 整数 N (1 ≦ N ≦ 100,000) 和 M (1 ≦ M ≦ 100,000) 用空格分隔。这是废墟 N 宝石 M 表示有不同的类型。
- 2 从行 N 行代表有关废墟的信息。 给出了 3 整数 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 以下所有宝石 1 表示一项一项获取。
积分分配及部分积分
这个问题是 101 设置满分、部分分数。
- N ≦ 8 和 如果您对 M ≦ 8 的数据集 如果您正确回答 1 , 给出30 点。
- N ≦ 5,000 和 如果您对 M ≦ 5,000 的数据集 如果您正确回答 2 的回答正确,除上述之外, 70 点。
- 没有附加约束的数据集 如果您正确回答 3 的回答正确,除上述之外, 1 点。
出力
无法复活魔王的可能搜索方法中获得的最高分。 在 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 。
你最终得到的宝石类型是宝石。 1 和珠宝 获取 2 和珠宝 获取 3 和珠宝 获取 6 的 4 型,魔王不会复活。总分是 80 点,这是最大值。
入力例2
2 7 1 3 90 5 7 90
出力例2
180
即使探索完所有遗迹,魔王也不会复活。
入力例3
1 4 1 4 70
出力例3
0
你无法探索遗迹以阻止魔王复活。