一家公司正在测试一种制取反物质的技术，反物质将用作行星际飞船的燃料。反物质通过在反应堆中进行特殊实验制得。

已知有 $n$ 种能够制取反物质的实验。进行第 $i$ 种实验后，反应堆的输出容器中会增加 $l_i$ 到 $r_i$ 克反物质。出于安全考虑，容器中积存的反物质不得超过 $a$ 克。

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

如果实验结束后容器中有 $t$ 克反物质，在反应堆中进行实验的总成本为 $s$，则利润为 $t\cdot10^9-s$。公司需要制定一种实验策略，使能够保证获得的利润最大化。

策略根据先前实验的结果决定接下来进行哪一种实验，或者决定停止继续实验。如果对于实验的任何可能结果，首先反应堆容器中的反物质不超过 $a$ 克，其次利润不少于 $x$，则称该策略能够保证获得利润 $x$。

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

请编写一个程序，确定能够保证获得的最大利润 $x$。

输入格式

第一行包含两个整数：$n$ 表示实验种类数，$a$ 表示容器中允许存放的反物质的最大数量（$1\le n\le100$，$1\le a\le2\,000\,000$）。

接下来 $n$ 行，每行包含三个整数 $l_i$、$r_i$ 和 $c_i$，分别表示第 $i$ 种实验所能产生的反物质的最小数量、最大数量以及该种实验的成本（$1\le l_i\le r_i\le a$，$1\le c_i\le100$）。

输出格式

输出一个整数，表示能够保证获得的最大利润 $x$。

样例

输入格式 1

1 17
4 6 10

输出格式 1

11999999970

输入格式 2

2 11
2 2 100
3 5 5

输出格式 2

9999999890

子任务