澄闪单挑骑士

时间限制：1000ms
内存限制：256Mib

题目背景

B 站 up 主“魔法 ZC 目录”是知名的《明日方舟》主播之一。

今天直播时他自信使用澄闪这名角色进入关卡“命运的宠儿”，单挑“猎潮的骑士”。

题目描述

我们假定澄闪的技能是在一瞬间将全场清屏，技能的冷却时间是 $T$ 秒。主播会选择一个时间开启技能，并且之后每当技能冷却时间结束后就会立即开启技能。具体地说，主播会选择一个非负整数时刻 $t$，而后在

这些时刻内分别在一瞬间消灭当前位于场上的所有敌方单位。

现在有 $n$ 个敌方单位。第 $i$ 个敌人会在 $l_i$ 时刻进入场内并停留到 $r_i$ 时刻（包含 $l_i,r_i$ 时刻），如果在这期间没有消灭这个敌人，他将消耗我方基地 $v_i$ 点生命值。

屏幕前的锐哥想知道，在主播无比聪明的前提下，我方最少会消耗多少点生命值。

输入格式

第一行两个正整数 $n,T$，含义如上。

接下来 $n$ 行，每行三个整数，其中的第 $i$ 行三个整数表示 $l_i,r_i,v_i$，含义如上。

输出格式

唯一一行一个整数，表示我方消耗的最少生命值。

输入样例

4 5
1 3 2
4 4 4
1 6 2
12 15 10

输出样例

2

样例解释

选择 $t=4$，可以在 $4,9,14,\cdots$ 这些时刻消灭位于场上的所有敌人。只有第一个敌人无法被消灭，消耗 2 点生命值。

数据范围与提示

对于 20% 的测试数据，$1 \le n \le 10;\ 1 \le l_i,r_i,T \le 100$。

对于 50% 的测试数据，$1 \le n \le 10^5;\ 1 \le l_i,r_i,T_i \le 10^5$。

对于 100% 的测试数据，$n \le 10^5;\ T \le 10^5;\ 1 \le l_i,r_i \le 10^9;\ v_i \le 10^4;\ l_i \le r_i$。