You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

魔力元素

题目背景

由于炼制神秘矿石炼制太多了，传奇炼金术师艾肯的魔力元素不够用了，于是他去向他的好朋友，传奇魔导师马克求助。

题目描述

马克有 $n$ 种获取魔力元素的实验，由于实验误差，第 $i$ 种实验至少能获得 $l_i$ 单位的魔力元素，至多能获得 $r_i$ 单位的魔力元素，且每次实验获得的魔力元素的单位都是整数。每次实验后生成的魔力元素都存放在一个容器中，但是抠门的马克的设备非常落后，这个容器最多能容纳 $a$ 单位的魔力元素，否则会爆炸。

马克每次实验可以选择任何一种实验进行，但是他只会选择使得容器一定不会爆炸的实验。马克可以进行任意次实验，在所有实验完成后，财迷的马克会把容器内的所有魔力元素以 $10^9$ 金币每单位的价格卖给财大气粗的艾肯。

现在马克已知第 $i$ 种实验的成本为 $c_i$ 金币，他想知道在最坏情况下自己最多可以保证获得多少金币的利润。

输入格式

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

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

输出格式

输出一行，一个整数，表示马克最多可以保证获得多少金币的利润。

样例 #1

样例输入 #1

1 17
4 6 10

样例输出 #1

11999999970

样例 #2

样例输入 #2

2 11
2 2 100
3 5 5

样例输出 #2

9999999890

样例解释1

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

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

数据范围

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