小藍(lán)正計(jì)劃進(jìn)行一次漫長(zhǎng)的旅行。小藍(lán)計(jì)劃開車完成這次旅行。顯然他在途中需要加油，否則可能無法完成這次旅行。

小藍(lán)要依次經(jīng)過 n 個(gè)地點(diǎn)，其中從第 i ? 1 個(gè)地點(diǎn)到達(dá)第 i 個(gè)地點(diǎn)需要消耗 Dis_i 升油。小藍(lán)經(jīng)過的每個(gè)地點(diǎn)都有一個(gè)加油站，但每個(gè)加油站的規(guī)定也不同。在第 i 個(gè)加油站加 1 升油需要 Cost_i 的費(fèi)用，且在這個(gè)加油站最多只能加 Lim_i 升油。

小藍(lán)的車的油箱也有容量限制，他的車上最多只能裝載 m 升油。 

一開始小藍(lán)的油箱是滿的，請(qǐng)問小藍(lán)需要準(zhǔn)備多少錢才能順利完成他的旅行計(jì)劃。如果小藍(lán)按給定條件無論準(zhǔn)備多少錢都不能完成他的旅行計(jì)劃，請(qǐng)輸出 ?1 。

輸入的第一行包含兩個(gè)整數(shù) n m ，用一個(gè)空格分隔。 

接下來 n 行每行包含 3 個(gè)整數(shù) Dis_i Cost_i Lim_i，相鄰整數(shù)之間使用一個(gè)空 格分隔。 

4 5
2 9 2
4 5 6
3 2 2
4 1 3

38

對(duì)于 30% 的評(píng)測(cè)用例，n Dis_i Cost_i Lim_i m ≤ 300 ；

對(duì)于 60% 的評(píng)測(cè)用例，n Dis_i Cost_i Lim_i m ≤ 5000 ； 

對(duì)于所有評(píng)測(cè)用例，1 ≤ n ≤ 2 × 10⁵，1 ≤ Dis_i Lim_i m ≤ 10⁹，1 ≤ Cost_i ≤ 40000 。