/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
高橋くんと青木くんは 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 より大きい点数にすることはできません。
高橋くんが勝つために必要な最小の勉強時間を出力してください。
制約
- 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)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
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 とする。
-
テスト 1 で 100 点、テスト 2 で 15 点とるように勉強する。
このとき 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
Score : 800 points
Problem Statement
Takahashi and Aoki will take N exams numbered 1 to N. They have decided to compete in these exams. The winner will be determined as follows:
-
For each exam i, Takahashi decides its importance c_i, which must be an integer between l_i and u_i (inclusive).
-
Let A be \sum_{i=1}^{N} c_i \times (Takahashi's score on Exam i), and B be \sum_{i=1}^{N} c_i \times (Aoki's score on Exam i). Takahashi wins if A \geq B, and Aoki wins if A < B.
Takahashi knows that Aoki will score b_i on Exam i, with his supernatural power.
Takahashi himself, on the other hand, will score 0 on all the exams without studying more. For each hour of study, he can increase his score on some exam by 1. (He can only study for an integer number of hours.) However, he cannot score more than X on an exam, since the perfect score for all the exams is X.
Print the minimum number of study hours required for Takahashi to win.
Constraints
- 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)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N X b_1 l_1 u_1 b_2 l_2 u_2 : b_N l_N u_N
Output
Print the minimum number of study hours required for Takahashi to win.
Sample Input 1
2 100 85 2 3 60 1 1
Sample Output 1
115
One optimal strategy is as follows:
-
Choose c_1 = 3, c_2 = 1.
-
Study to score 100 on Exam 1 and 15 on Exam 2.
Then, A = 3 \times 100 + 1 \times 15 = 315, B = 3 \times 85 + 1 \times 60 = 315 and Takahashi will win.
Sample Input 2
2 100 85 2 3 60 10 10
Sample Output 2
77
Sample Input 3
1 100000 31415 2718 2818
Sample Output 3
31415
Sample Input 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
Sample Output 4
2540