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