题目描述

你研发出了 $n$ 种获得反物质的实验，你无法控制生成的数量，但是可以保证第 $i$ 种获得的反物质在区间 $[l_i,r_i]$ 内，并且成本为 $c_i$，每种实验可以使用多次。

生成的反物质均会放在一个容器中，每次实验结束后，你可以得知容器中反物质的质量。容器中的反物质不能超过 $a$ 克（超过了就会爆炸）。

如果第 $i$ 次实验一共获得了 $t_i$ 单位的反物质，你可以将其卖给军方获得 $(10^9t_i-c)$ 卢布的利润，其中 $c$ 是该实验的成本。

在保证安全的前提下，你想要知道你最坏情况下利润至少是多少。

输入格式

第一行有两个整数 $n,a$。

接下来的 $n$ 行中，每行三个整数 $l_i,r_i,c_i$。

输出格式

输出一行，一个整数，表示你最多可以保证获得多少利润。

1 17
4 6 10

11999999970

2 11
2 2 100
3 5 5

9999999890

提示

【样例解释】

对于样例组 #1：

我们只能使用实验 $1$，如果实验一次，得到的反物质区间在 $[4,6]$ 内；实验两次，区间在 $[8,12]$，如果此时得到了 $12$ 单位的反物质就不能继续做实验了，因为如果下一次得到 $6$ 单位的话，容器就会爆炸；其他情况我们可以继续做第三次实验，可能的区间是 $[12,17]$。

这个时候无论如何都不能继续做实验了，原因同上，所以最坏情况下我们只能得到 $12$ 单位的反物质并且需要做三次实验，此时收益为 $3 \times (10^9 \times 4-10)=11999999970$。

【数据范围】

本题仅放了部分数据，如需评测完整数据请左转 LOJ P2772。

对于所有数据，$1 \le c_i \le 100$，$1 \le l_i \le r_i \le a$。

注：原题有 $15$ 个子任务，方便起见，最后若干组除 $a$ 数据范围外相同的子任务合并为 $1$ 组子任务。