题目描述

你已经放弃编程，搬到了三江平原开始务农。在田间劳作期间，你养成了一个规律的日常作息，现在每天恰好工作 $m$ 个时间单位。现在正值收获季节，你需要收获和处理 $n$ 种作物。对于作物类型 $i$，处理它一个时间单位将获得 $w_i$ 的利润。为了让日常工作不那么单调，对于每种作物类型 $i$，每天处理它的时间可以在 $[l_i, r_i]$ 的范围内选择一个整数。

某一天，天气预报说明天将有大雨，你将无法工作，因此你需要调整日程以便今天迅速收割作物。具体来说，你可以选择最多一种作物，并移除其每日时间范围的限制，使得处理该作物的时间可以是范围 $[0, m]$ 内的任意整数。其他作物的时间范围保持不变。你每天仍然需要恰好工作 $m$ 个时间单位。

你想知道今天能够获得的最大利润是多少。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \leq n \leq 10^5$, $1 \leq m \leq 10^{11}$)，分别表示作物的种类数和工作日的长度（单位：时间）。

接下来的 $n$ 行每行包含三个整数 $w_i$, $l_i$, 和 $r_i$ ($1 \leq w_i \leq 10^6$, $1 \leq l_i \leq r_i \leq 10^6$)，表示作物的利润和时间限制。

保证:$\sum_{i=1}^{n}l_{i}\le m \le \sum_{i=1}^{n}r_{i}$

输出格式

输出一个整数，表示今天能获得的最大利润。

样例

5 17
2 3 4
6 1 5
8 2 4
4 3 3
7 5 5

109