题目描述

高橋くんと青木くんは $1$ から $N$ までの番号がついたテストを受けようとしています。 二人はこのテストの結果を使って勝負することにしました。 具体的には、次のようにして勝敗を決めます。

• 高橋くんが各テスト $i$ について、その重要度 $c_i$ を決める。ただしこの値は $l_i$ 以上 $u_i$ 以下の整数である必要がある。
• $\sum_{i=1}^{N}\ c_i\ \times$ (高橋くんのテスト $i$ の点数) を $A$, $\$ $\sum_{i=1}^{N}\ c_i\ \times$ (青木くんのテスト $i$ の点数) を $B$ とする。 $A\ \geq\ B$ なら高橋くんの勝ち、$A\ <\ B$ なら青木くんの勝ち。

高橋くんはエスパーなので、青木くんがテスト $i$ で $b_i$ 点をとることがわかっています。

高橋くんはこのままだとすべてのテストで $0$ 点をとってしまいますが、 $1$ 時間勉強するごとに、好きなテストの点数を $1$ だけ上げることができます。($1$ 時間単位でしか勉強できません。) ただしテストはすべて $X$ 点満点なので、 $X$ より大きい点数にすることはできません。

高橋くんが勝つために必要な最小の勉強時間を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

高橋くんが勝つために必要な最小の勉強時間を出力せよ。

题目大意

给定非负整数序列 $\{l_n\},\{r_n\},\{b_n\},X$，求最小的 $s$，使得存在非负整数序列 $\{a_n\},\{c_n\}$，满足 $a_i\le X$，$\sum_{i=1}^na_i=s$，$c_i\in[l_i,r_i]$，且

所有输入均 $\le10^5$。

2 100
85 2 3
60 1 1

115

2 100
85 2 3
60 10 10

77

1 100000
31415 2718 2818

31415

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\ ≦\ N\ ≦\ 10^5$
• $1\ ≦\ X\ ≦\ 10^5$
• $0\ ≦\ b_i\ ≦\ X$ $(1\ \leq\ i\ \leq\ N)$
• $1\ ≦\ l_i\ ≦\ u_i\ ≦\ 10^5$ $(1\ \leq\ i\ \leq\ N)$
• 入力はすべて整数

Sample Explanation 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$ なので高橋くんが勝ちます。