题目描述

高桥君和青木君要参加编号从 $1$ 到 $N$ 的考试。他们打算用这些考试的结果来一决胜负。具体的胜负规则如下：

• 高桥君为每场考试 $i$ 决定其重要度 $c_i$，其中 $c_i$ 必须是 $l_i$ 到 $u_i$ 之间的整数。
• 记 $A = \sum_{i=1}^{N} c_i \times$（高桥君第 $i$ 场考试的分数），$B = \sum_{i=1}^{N} c_i \times$（青木君第 $i$ 场考试的分数）。如果 $A \geq B$，则高桥君获胜；如果 $A < B$，则青木君获胜。

高桥君是“超能力者”，他知道青木君在第 $i$ 场考试会得 $b_i$ 分。

目前高桥君所有考试的分数都是 $0$，但他可以通过学习来提高分数。每学习 $1$ 小时，可以任选一场考试的分数提升 $1$ 分（只能按小时为单位学习）。但每场考试的分数不能超过满分 $X$。

请输出高桥君获胜所需的最小学习时间。

输入格式

输入按以下格式从标准输入给出。

$N$ $X$ $b_1$ $l_1$ $u_1$ $b_2$ $l_2$ $u_2$ $\cdots$ $b_N$ $l_N$ $u_N$

输出格式

输出高桥君获胜所需的最小学习时间。

样例 1

输入

2 100
85 2 3
60 1 1

输出

115

样例 2

输入

2 100
85 2 3
60 10 10

输出

77

样例 3

输入

1 100000
31415 2718 2818

输出

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

输出

2540

说明/提示

限制条件

• $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$）
• 输入均为整数

样例解释 1

例如，最优的做法如下：

• 令 $c_1 = 3, c_2 = 1$。
• 通过学习使得第 $1$ 场考试得 $100$ 分，第 $2$ 场考试得 $15$ 分。 此时 $A = 3 \times 100 + 1 \times 15 = 315$，$B = 3 \times 85 + 1 \times 60 = 315$，因此高桥君获胜。

由 ChatGPT 4.1 翻译