题目描述

题目译自 ROI 2017 Day 2 T3. Антивещество

有 $n$ 种试验可以生成反物质。第 $i$ 种试验的成本为 $c_i$。你无法控制该试验会生成多少反物质，但知道该试验最少会生成 $l_i$ 克反物质，最多会生成 $r_i$ 克反物质。生成的反物质均会放在一个容器中，你可以得知容器中反物质的质量。容器中的反物质不能超过 $a$ 克。

军方想收购这些反物质，每克收购价为 $10^9$ 卢布。假设第 $i$ 种试验生成了 $t$ 克的反物质，则这次试验中你获得的利润为 $(t \times 10^9 - c_i)$ 卢布。

请问，在保证安全的情况下，你「最多」可以「保证」获得多少利润（即：最坏情况下的利润不超过多少）。

输入格式

第一行有两个整数 $n, a$。
在接下来的 $n$ 行中，每行三个整数 $l_i, r_i, c_i$。

输出格式

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

样例 1

输入

1 17
4 6 10

输出

11999999970

样例 2

输入

2 11
2 2 100
3 5 5

输出

9999999890

数据范围与提示

对于所有数据：

• $1 \leqslant n \leqslant 100$
• $1 \leqslant a \leqslant 2\times 10^6$
• $1 \leqslant l_i \leqslant r_i \leqslant a$
• $1 \leqslant c_i \leqslant 100$