分数: 800 点
问题陈述
高桥和青木将采取 N 考试编号 1 to N。 他们决定参加这些考试。 获胜者将按以下方式确定:
-
对于每次考试 i,高桥决定其 重要性 c_i,必须是介于 l_i 和 u_i (含)。
-
让 A be \sum_{i=1}^{N} c_i \times (高桥考试成绩 i),以及 B be \sum_{i=1}^{N} c_i \times (青木的考试成绩 i)。高桥获胜,如果 A \geq B,如果 A < B.
高桥知道青木会得分 b_i 考试 i,拥有他的神通。
另一方面,高桥本人将得分 0 无需学习即可完成所有考试。每学习一小时,他就可以在某些考试中提高分数 1。 (他只能学习整数小时。) 然而, 他得分不能超过 X 在考试中,因为所有考试的满分是 X.
打印高桥获胜所需的最少学习时间。
约束
- 1 \leq N \leq 10^5
- 1 \leq X \leq 10^5
- 0 \leq b_i \leq X (1 \leq i \leq N)
- 1 \leq l_i \leq u_i \leq 10^5 (1 \leq i \leq N)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N X b_1 l_1 u_1 b_2 l_2 u_2 : b_N l_N u_N
输出
打印高桥获胜所需的最少学习时间。
示例输入 1
2 100 85 2 3 60 1 1
示例输出 1
115
一种最佳策略如下:
-
选择 c_1 = 3, c_2 = 1.
-
学习评分 100 考试 1 和 15 考试 2.
然后, A = 3 \times 100 + 1 \times 15 = 315, B = 3 \times 85 + 1 \times 60 = 315 高桥将获胜。
示例输入 2
2 100 85 2 3 60 10 10
示例输出 2
77
示例输入 3
1 100000 31415 2718 2818
示例输出 3
31415
示例输入 4
10 1000 451 4593 6263 324 310 6991 378 1431 7068 71 1757 9218 204 3676 4328 840 6221 9080 684 1545 8511 709 5467 8674 862 6504 9835 283 4965 9980
示例输出 4
2540