{"raw_statement":[{"iden":"problem statement","content":"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:\n\n*   For each exam $i$, Takahashi decides its _importance_ $c_i$, which must be an integer between $l_i$ and $u_i$ (inclusive).\n    \n*   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$.\n    \n\nTakahashi knows that Aoki will score $b_i$ on Exam $i$, with his supernatural power.\nTakahashi 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$.\nPrint the minimum number of study hours required for Takahashi to win."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq X \\leq 10^5$\n*   $0 \\leq b_i \\leq X$ $(1 \\leq i \\leq N)$\n*   $1 \\leq l_i \\leq u_i \\leq 10^5$ $(1 \\leq i \\leq N)$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $X$\n$b_1$ $l_1$ $u_1$\n$b_2$ $l_2$ $u_2$\n$:$\n$b_N$ $l_N$ $u_N$"},{"iden":"sample input 1","content":"2 100\n85 2 3\n60 1 1"},{"iden":"sample output 1","content":"115\n\nOne optimal strategy is as follows:\n\n*   Choose $c_1 = 3, c_2 = 1$.\n    \n*   Study to score $100$ on Exam $1$ and $15$ on Exam $2$.\n    \n\nThen, $A = 3 \\times 100 + 1 \\times 15 = 315$, $B = 3 \\times 85 + 1 \\times 60 = 315$ and Takahashi will win."},{"iden":"sample input 2","content":"2 100\n85 2 3\n60 10 10"},{"iden":"sample output 2","content":"77"},{"iden":"sample input 3","content":"1 100000\n31415 2718 2818"},{"iden":"sample output 3","content":"31415"},{"iden":"sample input 4","content":"10 1000\n451 4593 6263\n324 310 6991\n378 1431 7068\n71 1757 9218\n204 3676 4328\n840 6221 9080\n684 1545 8511\n709 5467 8674\n862 6504 9835\n283 4965 9980"},{"iden":"sample output 4","content":"2540"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}