Background

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

Description

我们假定澄闪的技能是在一瞬间将全场清屏，技能的冷却时间是 $T$ 秒。主播会选择一个时间开启技能，并且之后每当技能冷却时间结束后就会立即开启技能。具体地说，主播会选择一个非负整数时刻 $t$ ，而后在 $t, t + T, t + 2T, · · ·$ 这些时刻内分别在一瞬间消灭当前位于场上的所有敌方单位。

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

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

Format

Input

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

接下来 $n$ 行，每行两个整数，其中的第 $i$ 行三个整数表示 $li, ri, vi$，含义如上。

Output

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

Samples

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

2

【样例解释】

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

Limitation

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

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

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