output_description: Print the minimum number of study hours required for Takahashi to win.
  
  * * *
input_description: 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
attempt: #!/usr/bin/env python3
  import sys
  
  INF = float("inf")
  from itertools import accumulate
  import heapq
  
  
  def solve(N: int, X: int, b: "List[int]", l: "List[int]", u: "List[int]"):
  
      # i番目のテストで高橋くんがx点とったとき、A-Bに加える量
      def f(i, x):
          if x <= b[i]:
              return l[i] * (x - b[i])
          else:
              return u[i] * (x - b[i])
  
      # あらかじめ、0点とった時とX点とった時の効果が大きい順に並べておく
      mh = [[f(i, X) - f(i, 0), i] for i in range(N)]
      mh.sort(reverse=True)
      mX = [f(i, X) for _, i in mh]
      mXacc = list(accumulate(mX))
      m0 = [f(i, 0) for _, i in mh]
      m0acc = list(accumulate(m0))
      # print(mh)
      # print(mX)
      # print(mXacc)
      # print(m0)
      # print(m0acc)
  
      def isOK(index, key):
          # 勉強時間Tとしてスコア(A-B)を最大化するよう勉強時間を配分する
          T = index
          num = 1 + T // X  # 点をとるテストの個数
          # print(num)
          # いったんX点とらせる
          # D = sum([f(i, X) for _, i in mh[:num]])\
          #     + sum([f(i, 0) for _, i in mh[num:]])
          # print(D)
          # print("A", mXacc[num-1])
          # print("B", m0acc[-1]-m0acc[num-1])
          D = mXacc[num - 1] + m0acc[-1] - m0acc[num - 1]
          # print(D)
          # 点を取るテストの中で、点数をT%X点に変更した時、
          # 最も減少の小さいものを選ぶ
          a = [0] * N
          for _, j in mh[:num]:
              a[j] = X
          if num != 0:
              v, i = min([[f(i, X) - f(i, T % X), i] for _, i in mh[:num]])
              D -= v
              a[i] = T % X
          # print(D)
          # print(a)
          return D >= key
  
      def binary_search(key):
          ng = -1
          ok = N * X
          while abs(ok - ng) > 1:
              mid = (ok + ng) // 2
              # print("ng, mid, ok = {}, {}, {}".format(ng, mid, ok))
              if isOK(mid, key):
                  ok = mid
              else:
                  ng = mid
          return ok
  
      ans = binary_search(0)
      print(ans)
      return
  
  
  def main():
  
      def iterate_tokens():
          for line in sys.stdin:
              for word in line.split():
                  yield word
  
      tokens = iterate_tokens()
      N = int(next(tokens))  # type: int
      X = int(next(tokens))  # type: int
      b = [int()] * (N)  # type: "List[int]"
      l = [int()] * (N)  # type: "List[int]"
      u = [int()] * (N)  # type: "List[int]"
      for i in range(N):
          b[i] = int(next(tokens))
          l[i] = int(next(tokens))
          u[i] = int(next(tokens))
      solve(N, X, b, l, u)
  
  
  if __name__ == "__main__":
      main()
  
problem_description: 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.
samples: [{"input": "2 100\n    85 2 3\n    60 1 1", "output": "115\n    \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\nThen, A = 3 \\times 100 + 1 \\times 15 = 315, B = 3 \\times 85 + 1 \\times 60 =\n315 and Takahashi will win.\n\n* * *"}, {"input": "2 100\n    85 2 3\n    60 10 10", "output": "77\n    \n\n* * *"}, {"input": "1 100000\n    31415 2718 2818", "output": "31415\n    \n\n* * *"}, {"input": "10 1000\n    451 4593 6263\n    324 310 6991\n    378 1431 7068\n    71 1757 9218\n    204 3676 4328\n    840 6221 9080\n    684 1545 8511\n    709 5467 8674\n    862 6504 9835\n    283 4965 9980", "output": "2540"}]