一家公司正在测试一种用于星际飞船燃料的反物质获取技术。反物质是通过在反应堆中进行特殊实验产生的。

已知有 $n$ 种实验可以产生反物质。进行第 $i$ 种实验后，反应堆的输出容器中会增加 $l_i$ 到 $r_i$ 克反物质。出于安全考虑，禁止容器中积累超过 $a$ 克反物质。

进行第 $i$ 种实验的成本为 $c_i$，每克产生的反物质价值为 $10^9$。

如果在进行实验后容器中产生了 $t$ 克反物质，且实验的总成本为 $s$，则利润由公式 $(t \cdot 10^9 - s)$ 确定。公司需要制定一种实验策略，以最大化可以保证获得的利润。

根据之前实验的结果，策略决定接下来应该进行哪种类型的实验，或者决定停止进一步的实验。如果对于任何实验结果，策略都能保证：第一，反应堆容器中的反物质不超过 $a$ 克；第二，利润至少为 $x$，则称该策略保证获得利润 $x$。

例如，假设只有一种类型的实验，产生 4 到 6 克反物质，成本为 10，容器容量为 17 克。那么在进行两次实验后，容器中可能有 8 到 12 克反物质。如果产生了 12 克，则不能再进行实验，因为如果再产生 6 克反物质，容器可能会溢出。在其他情况下，可以进行第三次实验，并获得 12 到 17 克反物质。在最坏的情况下，必须进行三次实验，总成本为 30，利润为 $(12 \cdot 10^9 - 30) = 11\,999\,999\,970$。

你需要编写一个程序，确定可以保证获得的最大利润 $x$。

输入格式

第一行包含两个整数：$n$ — 实验类型的数量，$a$ — 容器中允许的最大反物质数量 ($1 \le n \le 100, 1 \le a \le 2\,000\,000$)。

接下来的 $n$ 行，每行包含三个整数 $l_i, r_i$ 和 $c_i$ — 分别为第 $i$ 种实验产生的反物质的最小和最大数量，以及该实验的成本 ($1 \le l_i \le r_i \le a, 1 \le c_i \le 100$)。

输出格式

输出一个整数 — 可以保证获得的最大利润 $x$。

样例

输入 1

1 17
4 6 10

输出 1

11999999970

输入 2

2 11
2 2 100
3 5 5

输出 2

9999999890

子任务