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.