题目描述

题目译自 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 17
4 6 10

11999999970

2 11
2 2 100
3 5 5

9999999890

数据范围与提示

对于所有数据，$1 ⩽ n ⩽ 100,$ $1 ⩽ a ⩽ 2\times 10^6,$ $1 ⩽ l_i ⩽ r_i ⩽ a,$ $1 ⩽ c_i ⩽ 100$。