一家公司正在測試製造反物質的技術，反物質將用作行星間飛船的燃料。反物質由反應爐中的特殊實驗產生。

已知有 $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

子任務