题目描述

Takahashi 和 Aoki 将参加编号为 $1$ 到 $N$ 的 $N$ 个考试。他们决定在这些考试中展开竞争。获胜者的决定方法如下：

• 对于每个考试 $i$，Takahashi 决定其_重要性_ $c_i$，其中 $c_i$ 必须是介于 $l_i$ 和 $u_i$ 之间的整数。

• 让 $A$ 为 $\\sum_{i=1}^{N} c_i \\times$ (Takahashi 在考试 $i$ 上的得分)，$B$ 为 $\\sum_{i=1}^{N} c_i \\times$ (Aoki 在考试 $i$ 上的得分)。如果 $A \\geq B$，则 Takahashi 获胜，如果 $A < B$，则 Aoki 获胜。

Takahashi 知道 Aoki 会在考试 $i$ 上取得得分 $b_i$，并且这是他的超能力。另一方面，Takahashi 不做任何学习将获得所有考试的零分。他每多学习一小时，就可以将某个考试的得分提高 $1$ 分。(他只能以整数小时进行学习。)然而，他不能在某个考试上获得超过 $X$ 分，因为所有考试的满分都是 $X$。

请输出 Takahashi 赢得比赛所需的最小学习小时数。

约束条件

• $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$

输出

请输出 Takahashi 赢得比赛所需的最小学习小时数。

示例输入1

2 100
85 2 3
60 1 1

示例输出1

115

一种最优策略如下：

• 选择 $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$，Takahashi 将获胜。

示例输入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