[ROI 2017] 反物质 (Day 2)

你研发出了 $n$ 种获得反物质的实验，你无法控制生成的数量，但是可以保证第 $i$ 种获得的反物质在区间 $[l_i,r_i]$ 内，并且成本为 $c_i$，每种实验可以使用多次。 生成的反物质均会放在一个容器中，每次实验结束后，你可以得知容器中反物质的质量。容器中的反物质不能超过 $a$ 克（超过了就会爆炸）。 如果第 $i$ **次**实验一共获得了 $t_i$ 单位的反物质，你可以将其卖给军方获得 $(10^9t_i-c)$ 卢布的利润，其中 $c$ 是该实验的成本。 在保证安全的前提下，你想要知道你最坏情况下利润至少是多少。 ## Input 第一行有两个整数 $n,a$。 接下来的 $n$ 行中，每行三个整数 $l_i,r_i,c_i$。 ## Output 输出一行，一个整数，表示你最多可以保证获得多少利润。 [samples] ## Note #### 【样例解释】 对于样例组 #1： 我们只能使用实验 $1$，如果实验一次，得到的反物质区间在 $[4,6]$ 内；实验两次，区间在 $[8,12]$，如果此时得到了 $12$ 单位的反物质就不能继续做实验了，因为如果下一次得到 $6$ 单位的话，容器就会爆炸；其他情况我们可以继续做第三次实验，可能的区间是 $[12,17]$。 这个时候无论如何都不能继续做实验了，原因同上，所以最坏情况下我们只能得到 $12$ 单位的反物质并且需要做三次实验，此时收益为 $3 \times (10^9 \times 4-10)=11999999970$。 #### 【数据范围】 本题仅放了部分数据，如需评测完整数据请左转 [LOJ P2772](https://loj.ac/p/2772)。 对于所有数据，$1 \le c_i \le 100$，$1 \le l_i \le r_i \le a$。 | 子任务编号 | 分值 | $1 \le n \le$ | $1 \le a \le$ | 特殊限制 | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $1$ | $10^3$ | 无 | | $2$ | $10$ | $10$ | $10^3$ | $l_i=r_i$ | | $3$ | $20$ | $10$ | $10^3$ | 无 | | $4$ | $20$ | $100$ | $5 \times 10^4$ | 无 | | $5$ | $40$ | $100$ | $2 \times 10^6$ | 无 | 注：原题有 $15$ 个子任务，方便起见，最后若干组除 $a$ 数据范围外相同的子任务合并为 $1$ 组子任务。