题目描述

你放弃了编程，来到了三江平原开始务农。在劳动过程中你改掉了作息不规律的毛病，每天你都 $\textbf{恰好}$ 工作 $m$ 个单位时间。现在到了收获的季节，你需要收割并加工你种植的 $n$ 种作物，对于第 $i$ 种作物，处理一单位时间该种作物将获得 $w_i$ 的收益。为了使每天的工作不会太单调，对于第 $i$ 种作物，你每天处理它的总时间长度可以是 $[l_i, r_i]$ 范围内的整数。

某天，天气预报说第二天的天气不好，于是在今天你需要调整时间安排以尽快抢收作物。具体地说，你能最多选择一种作物，并删除每天处理这种作物的时间范围限制，即删除后处理该作物的总时间长度可以是 $[0, m]$ 范围内的任意整数，而处理其他作物的时间范围不变。你仍然在这一天 $\textbf{恰好}$ 工作 $m$ 个单位时间。

你想知道满足上述条件的情况下，这一天能获得的最大收益是多少。

输入格式

第一行两个整数 $n$ 和 $m$ ($1 \le n \le 10^5$, $1 \le m \le 10^{11}$)，分别表示作物种类数和一天工作时间长度。

接下来 $n$ 行，每行三个整数 $w_i$, $l_i$, 和 $r_i$ ($1 \le w_i \le 10^6$, $1 \le l_i \le r_i \le 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