AT_agc034_c [AGC034C] Tests

高桥君和青木君要参加编号从 $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 \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 翻译