#2772. 「ROI 2017 Day 2」反物质

内存限制:128 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: Planet6174

题目描述

题目译自 ROI 2017 Day 2 T3. Антивещество

n 种试验可以生成反物质。第 i 种试验的成本为 c_i 。你无法控制该试验会生成多少反物质,但知道该试验最少会生成 l_i 克反物质,最多会生成 r_i 克反物质。生成的反物质均会放在一个容器中,你可以得知容器中反物质的质量。容器中的反物质不能超过 a 克。
军方想收购这些反物质,每克收购价为 10^9 卢布。假设第 i 种试验生成了 t 克的反物质,则这次试验中你获得的利润为 (t\times 10^9-c_i) 卢布。
请问,在保证安全的情况下,你「最多」可以「保证」获得多少利润(即:最坏情况下的利润不超过多少)。

输入格式

第一行有两个整数 n, a
在接下来的 n 行中,每行三个整数 l_i, r_i, c_i

输出格式

输出一行,一个整数,表示你最多可以保证获得多少利润。

样例

样例输入 1

1 17
4 6 10

样例输出 1

11999999970

样例输入 2

2 11
2 2 100
3 5 5

样例输出 2

9999999890

数据范围与提示

对于所有数据, 1 ⩽ n ⩽ 100, 1 ⩽ a ⩽ 2\times 10^6, 1 ⩽ l_i ⩽ r_i ⩽ a, 1 ⩽ c_i ⩽ 100

子任务 分值 n a 额外条件
1 10 n = 1 1 ⩽ a ⩽ 1 000
2  10  1 ⩽ n ⩽ 10 l_i = r_i
3 20
4  20  1 ⩽ n ⩽ 100
(知道你会看瞎眼
提醒你一下
这里总共 70 分)
1 ⩽ a ⩽ 5\times 10^4
5 4 1 ⩽ a ⩽ 1\times 10^5
6  4  1 ⩽ a ⩽ 2\times 10^5
7 4 1 ⩽ a ⩽ 3\times 10^5
8  4  1 ⩽ a ⩽ 4\times 10^5
9 4 1 ⩽ a ⩽ 5\times 10^5
10  4  1 ⩽ a ⩽ 8\times 10^5
11 4 1 ⩽ a ⩽ 1.1\times 10^6
12  4  1 ⩽ a ⩽ 1.4\times 10^6
13 4 1 ⩽ a ⩽ 1.7\times 10^6
14  4  1 ⩽ a ⩽ 2\times 10^6