Problem:
 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

Solution (Python):

"""

https://atcoder.jp/contests/agc034/tasks/agc034_c

cをどうやって決めるか考える
差分で考えることとする
負けることにする場合、cが大きいほど負けがかさむので l
そうでない場合、重要度を uにするべき

勝ちを増やす or 負けを減らすの、どっちの方が良い…？

bが小さいほうを勝ち、大きいほうを負けにした方がいい説
bが小さいほうで負け、大きいほうで勝つ場合を考えてみる
a1 < b1 < b2 < a2 とする。
この時、寄与は (a2-b2)*u2-(b1-a1)*l1 = X
aの値を交換してみると、寄与は
(a2-b1)*u1 - (b2-a1) * l2 = Y
となる。
Y-X = 
となり改善するので示された

bが小さいほうからi個を勝ちにする場合の最小を考えればいい
→あとは全探索すれば終わり

うわー luは固定じゃないんかい
とりあえず勝ち負けを決めた場合のスコア計算を考えてみる
最初全部負けで考え、損失の和Pを計算しておく→Σbi*li
N個のコインタワーがあり、上からbi個の価値はli、残りはuiである
Pを超える価値を取るための最小の枚数を求めよ
上を取っておいて下を取らない意味がないので、取ると決めたら山全部取るのが最適
→山の総和が大きい順にソート
→最大の山を全部取っても足りない場合、取りつくす
→最後の1山は残りから全探索する

なぜWA?
分からん…
山を上からとらない理由がない

4,4,93 →和101
2,2,96 →和100
104
→大きいほうからとっていいなんてことはなかった
→総和が大きい山を必ずすべて使うという未証明命題を使おうとしたのが敗因

"""

from sys import stdin

N,X = map(int,stdin.readline().split())

P = 0
sblu = [] 

for i in range(N):
    b,l,u = map(int,stdin.readline().split())
    s = b * l + (X-b) * u
    P += b * l
    sblu.append((s,b,l,u))

sblu.sort()
sblu.reverse()

ans = float("inf")
slis = []
for i in range(N):
    if i == 0:
        slis.append(sblu[i][0])
    else:
        slis.append(slis[-1] + sblu[i][0])

for i in range(N): 

    
    L = -1
    R = N-1
    while R-L != 1:
        
        M = (R+L)//2
        if M < i:
            if slis[M] + sblu[i][0] >= P:
                R = M
            else:
                L = M
        else:
            if slis[M] >= P:
                R = M
            else:
                L = M

    if R < i:
        rem = P - slis[R]
        nans = X * (R+1)
    else:
        rem = P - (slis[R]-sblu[i][0])
        nans = X * R

    if rem < 0 or sblu[i][0] < rem:
        continue

    s,b,l,u = sblu[i]
    if rem <= b*l:
        nans += (rem+l-1) // l
    else:
        rem = rem - b * l
        nans += b + (rem+u-1)//u

    ans = min(ans,nans)

print (ans)

Solution (Python):
N,X=map(int,input().split())
t=[]
s=0
for i in range(N):
    b,l,u=map(int,input().split())
    t.append(((X-b)*u+l*b,b,l,u))
    s-=b*l
t.sort()
def condition(q):
    check=sum(t[i][0] for i in range(N-q,N))
    return check+s>=0

start=0
end=N
while end-start>1:
    test=(end+start)//2
    if not condition(test):
        start=test
    else:
        end=test

if not condition(end):
    Q=end
else:
    Q=start

check=sum(t[i][0] for i in range(N-Q,N))
check2=check+t[N-Q-1][0]
def condition2(r):
    M=0
    for i in range(N):
        test=0
        if N-Q>i:
            test=check
            val,b,l,u=t[i]
            if b>=r:
                test+=r*l
            else:
                test+=r*u-b*(u-l)
            M=max(M,test)
        else:
            val,b,l,u=t[i]
            test=check2-val
            if b>=r:
                test+=r*l
            else:
                test+=r*u-b*(u-l)
            M=max(M,test)
    return M+s>=0

start=0
end=X-1
while end-start>1:
    mid=(end+start)//2
    if condition2(mid):
        end=mid
    else:
        start=mid

if condition2(start):
    R=start
elif condition2(end):
    R=end
else:
    R=X
print(Q*X+R)

Solution (Python):
N,X=map(int,input().split())
blu=[list(map(int,input().split())) for i in range(N)]

S=0
data=[]

low=0
high=0

for i in range(N):
    b,l,u=blu[i]
    high+=b
    data.append([u*(X-b)+l*b,i])
    S-=b*l
data.sort(reverse=True)

lst=[data[0][0]]
lsls=[data[0][1]]
for i in range(1,N):
    lst.append(lst[-1]+data[i][0])
    lsls.append(data[i][1])

while high-low>1:
  
    mid=(high+low)//2
    ppp=mid//X
    qqq=mid%X
    
    SS=S
    if ppp>0:
        SS+=lst[ppp-1]
    num=0
    for i in range(ppp,N):
        b,l,u=blu[lsls[i]]
        if qqq>=b:
            num1=b*l+(qqq-b)*u
        else:
            num1=qqq*l
        num=max(num,num1)
    SS+=num
    
    SSS=S+lst[ppp]
    num=-float("inf")
    for i in range(ppp):
        zzz,ind=data[i]
        b,l,u=blu[ind]
        if qqq>=b:
            num1=-zzz+b*l+(qqq-b)*u
        else:
            num1=-zzz+qqq*l
        num=max(num,num1)
    SSS+=num
    
    SS=max(SS,SSS)
    if SS>=0:
        high=mid
    else:
        low=mid

print(high)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())
X = []
s = 0
for _ in range(N):
    b, l, u = map(int, input().split())
    t = M * u - (u - l) * b
    X.append((t, b, l, u))
    s += b * l

X = sorted(X, key = lambda x: -x[0])
A = [0] + [x[0] for x in X]
for i in range(1, N+1):
    A[i] += A[i-1]

def sum_excl(i, j):
    return A[j] if j <= i else A[j] - X[i][0]

def chk(i):
    t, bb, ll, uu = X[i]
    l, r = -1, N + 1
    while r - l > 1:
        m = (l + r) // 2
        if sum_excl(i, m) + t >= s:
            r = m
        else:
            l = m
    re = (r - (i < r)) * M
    rem = s - sum_excl(i, r)
    l, r = -1, M + 1
    while r - l > 1:
        m = (l + r) // 2
        if (m * uu - (uu - ll) * bb if m > bb else m * ll) >= rem:
            r = m
        else:
            l = m
    re += r
    return re

print(min(chk(i) for i in range(N)))

Solution (Python):
"""

重要度はlかuしかとらないと考えてよい
高橋君のほうが青木君より低い点数を取ると決めた科目に対してはl、それ以外はuと定める
それぞれのテストの点数の差をdとして、Σ[a>=b](d*u) - Σ[a<b](d*l) >= 0 を満たす
最小のΣaを求める
→各iについて、biまではli個ずつ減らすことができ、それより多く減らす場合はXを超えない範囲で
 ui個ずつ減らすことができる
→heapqでできそう
 単純なheapqだと、例えば一つのテストの中でlとuの値の差がとても大きい時に
 正しい答えが出せない
→二分探索

"""
import sys
input = sys.stdin.readline

n, x = map(int, input().split())
BLU = [list(map(int, input().split())) for _ in range(n)]
SBLU = sorted([(b*l+(x-b)*u, b, l, u) for b, l, u in BLU], reverse=True)
S, B, L, U = zip(*SBLU)
M = sum([b*l for b, l, u in BLU])

def select(q, r):
  f = sum(S[:q+1])
  for i in range(n):
    temp = f - S[min(i, q)]
    temp += L[i]*min(B[i], r) + U[i]*max(r-B[i], 0)
    if temp>=M:
      return True
  return False


ng = -1
ok = sum(B)
while ok-ng > 1:
  mid = (ok+ng)//2
  q, r = divmod(mid, x)
  if select(q, r):
    ok = mid
  else:
    ng = mid
print(ok)

Solution (Python):







def accumulate(a):
    """初項0"""
    su = 0
    yield su

    for x in a:
        su += x
        yield su


















def solve_agc034c():
    from bisect import bisect_left
    from collections import namedtuple
    import sys
    input = sys.stdin.readline
    

    Test = namedtuple('Test', 'Aoki_score lower_bound upper_bound')
    Test.Merit = lambda self, Takahashi_score: \
        self.lower_bound * Takahashi_score if Takahashi_score <= self.Aoki_score \
            else self.upper_bound * Takahashi_score - (self.upper_bound - self.lower_bound) * self.Aoki_score

    N, X = map(int, input().split())
    tests = []
    for _ in range(N):
        row = map(int, input().split())
        tests.append(Test(*row))
    tests.sort(key=lambda test: test.Merit(Takahashi_score=X), reverse=True)
    

    need = sum(test.lower_bound * test.Aoki_score for test in tests)

    *acc, = accumulate(test.Merit(Takahashi_score=X) for test in tests)

    bi = bisect_left(acc, need)  
    if bi == 0:
        print(0)  
        return

    ge_need = acc[bi]  
    lt_need = acc[bi - 1]  

    def generate_candidates():
        INF = 10 ** 20
        for i, p in enumerate(tests, start=1):
            
            if i < bi:
                rest = need - (ge_need - p.Merit(Takahashi_score=X))
            else:
                rest = need - lt_need

            if rest <= p.Merit(Takahashi_score=p.Aoki_score):
                
                add_ = (rest + p.lower_bound - 1) // p.lower_bound
            else:
                
                add_ = p.Aoki_score
                add_ += (rest - p.Merit(Takahashi_score=p.Aoki_score) + p.upper_bound - 1) // p.upper_bound

            if add_ > X:
                yield INF
            else:
                ret = X * (bi - 1) + add_
                yield ret

    gen = generate_candidates()
    res = min(gen)
    print(res)
    return


if __name__ == '__main__':
    solve_agc034c()

Solution (Python):







def accumulate(a):
    """初項0"""
    su = 0
    yield su

    for x in a:
        su += x
        yield su


















def solve_agc034c():
    from bisect import bisect_left
    from collections import namedtuple
    import sys
    input = sys.stdin.readline
    

    Test = namedtuple('Test', 'Aoki_score lower_bound upper_bound')
    Test.Merit = lambda self, Takahashi_score: \
        self.lower_bound * Takahashi_score if Takahashi_score <= self.Aoki_score \
            else self.upper_bound * Takahashi_score - (self.upper_bound - self.lower_bound) * self.Aoki_score

    N, X = map(int, input().split())
    tests = []
    for _ in range(N):
        row = map(int, input().split())
        tests.append(Test(*row))
    tests.sort(key=lambda test: test.Merit(Takahashi_score=X), reverse=True)
    

    need = sum(test.lower_bound * test.Aoki_score for test in tests)

    *acc, = accumulate(test.Merit(Takahashi_score=X) for test in tests)

    bi = bisect_left(acc, need)  
    if bi == 0:
        print(0)  
        return

    ge_need = acc[bi]  
    lt_need = acc[bi - 1]  

    def generate_candidates():
        INF = 10 ** 20
        for i, p in enumerate(tests, start=1):
            
            if i < bi:
                rest = need - (ge_need - p.Merit(Takahashi_score=X))
            else:
                rest = need - lt_need

            if rest <= p.Merit(Takahashi_score=p.Aoki_score):
                
                add_ = (rest + p.lower_bound - 1) // p.lower_bound
            else:
                
                add_ = p.Aoki_score
                add_ += (rest - p.Merit(Takahashi_score=p.Aoki_score) + p.upper_bound - 1) // p.upper_bound

            if add_ > X:
                yield INF
            else:
                ret = X * (bi - 1) + add_
                yield ret

    gen = generate_candidates()
    res = min(gen)
    print(res)
    return


if __name__ == '__main__':
    solve_agc034c()

Solution (Python):

def accumulate(a):
    su = 0
    yield su

    for x in a:
        su += x
        yield su


def solve_agc034c():
    from collections import namedtuple
    import sys
    input = sys.stdin.readline

    Test = namedtuple('Test', 'Aoki_score lower_bound upper_bound')
    Test.D_partial = lambda self, score: \
        self.lower_bound * score if score <= self.Aoki_score \
            else self.upper_bound * score - (self.upper_bound - self.lower_bound) * self.Aoki_score

    def is_ok(init_rest):
        """init_rest: 勉強に使える時間"""
        take, rest = divmod(init_rest, X)
        if take > N - 1:
            r = take - (N - 1)
            take = N - 1
            rest += r * X

        for i, partial_solve_test in enumerate(tests, start=1):
            when_full = partial_solve_test.D_partial(X)
            if i <= take:
                su = acc[take + 1] - when_full
            else:
                su = acc[take]

            when_partial = partial_solve_test.D_partial(min(X, rest))
            d = INIT_D + su + when_partial
            if d >= 0:
                return True

        return False

    def binary_search(*, ok, ng, is_ok):
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    N, X = map(int, input().split())
    tests = []
    for _ in range(N):
        row = map(int, input().split())
        tests.append(Test(*row))
    tests.sort(key=lambda test: test.D_partial(X), reverse=True)
    
    
    

    INIT_D = -sum(test.lower_bound * test.Aoki_score for test in tests)

    *acc, = accumulate(test.D_partial(X) for test in tests)

    res = binary_search(ok=10 ** 10, ng=-1, is_ok=is_ok)
    

    print(res)
    return


if __name__ == '__main__':
    solve_agc034c()

Solution (Python):
import sys
input = sys.stdin.readline

from itertools import accumulate

def main():
    N,X=map(int,input().split())
    A=[list(map(int,input().split())) for i in range(N)]

    A.sort(key=lambda x:x[2]*(X-x[0])+x[0]*x[1],reverse=True)
    ALL=[a[2]*(X-a[0])+a[0]*a[1] for a in A]



    SUM=[0]+list(accumulate(ALL))

    MAX=0
    MINUS=0

    for a,r,l in A:
        MAX+=a
        MINUS+=a*r

    OUT=-1

    def binsearch(score):

        alluse=score//X
        rest=score-alluse*X

        for ri in range(N):
            plus=0
            b,l,u=A[ri]
            
            if rest<b:
                plus+=rest*l
            else:
                plus+=rest*u+b*l-b*u

            if alluse<=ri:
                plus+=SUM[alluse]

            else:
                plus+=SUM[alluse+1]-ALL[ri]

            

            if plus>=MINUS:
                return 1

        return 0


    while MAX-OUT>1:
        mid=(MAX+OUT)//2

        if binsearch(mid)==1:
            MAX=mid
        else:
            OUT=mid

    print(MAX)

main()

Solution (Python):
import sys
input = sys.stdin.readline

import numpy as np

N,X = map(int,input().split())
B,L,U = np.array([input().split() for _ in range(N)],dtype=np.int64).T

target = (B*L).sum()

full_score = B*L + U*(X-B)
i = full_score.argsort()[::-1]
B = B[i]; L = L[i]; U = U[i]; full_score = full_score[i]
full_score_cum = full_score.cumsum()

def test(x):
    
    q,r = divmod(x,X)
    
    q_part = np.zeros_like(B)
    if q >= 1:
        q_part[q:] = full_score_cum[q-1]
        q_part[:q] = full_score_cum[q] - full_score[:q]
    r_part = np.where(r<=B,L*r,B*L+(r-B)*U)
    return (q_part + r_part).max() >= target

left = -1
right = X*N

while left + 1 < right:
    mid = (left + right)//2
    if test(mid):
        right = mid
    else:
        left = mid

answer = right
print(answer)

Solution (Python):
N, X = map(int, input().split())
blu = []
scores = []
opponent = 0
for i in range(N):
    b, l, u = map(int, input().split())
    blu.append((b, l, u))
    scores.append(((X-b)*u + l*b, i))
    opponent += b * l

scores_sorted = sorted(scores, reverse=True)
cum = [scores_sorted[0][0]]
for i in range(1, N):
    cum.append(cum[-1] + scores_sorted[i][0])


def calc_X(k):
    ret = -opponent
    n = k // X
    m = k % X
    if n == N:
        return cum[n-1] - opponent

    for i in range(N):
        temp = 0
        b, l, u = blu[i]
        if n > 0:
            if scores[i][0] >= scores_sorted[n-1][0]:
                temp = (cum[n] - opponent) - scores[i][0]
            else:
               temp = cum[n-1] - opponent
        else:
            temp = -opponent
        if m > b:
            temp += (m-b) * u + b * l
        else:
            temp += (m-b) * l + b * l
        ret = max(ret, temp)
    return ret
        
left = 0
right = N*X

while right - left > 1:
    mid = (left + right) // 2
    if calc_X(mid) >= 0:
        right = mid
    else:
        left = mid

if calc_X(left) >= 0:
    print(left)
else:
    print(right)

Solution (Python):



""" convenient functions




"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations 

from math import factorial, ceil, floor
def factorize(n):
    """return the factors of the Arg and count of each factor
    
    Args:
        n (long): number to be resolved into factors
    
    Returns:
        list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
    """
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct
def combinations_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    
    if n < 0 or r < 0:
        raise Exception('combinations_count(n, r) not defined when n or r is negative')
    if n - r < r: r = n - r
    if r < 0: return 0
    if r == 0: return 1
    if r == 1: return n
    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]
    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])
    return result
def combinations_with_replacement_count(n, r):
    """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
    
    Args:
        n (long): number
        r (long): number
    
    Raises:
        Exception: not defined when n or r is negative
    
    Returns:
        long: number
    """
    if n < 0 or r < 0:
        raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
    elif n == 0:
        return 1
    else:
        return combinations_count(n + r - 1, r)
from bisect import bisect_left, bisect_right
from collections import deque, Counter, defaultdict 
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest 
from copy import deepcopy, copy 
from operator import itemgetter


from functools import reduce
def chmin(x, y):
    """change minimum
    if x > y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current minimum value
        y (long): potential minimum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x > y:
        x = y
        return (x, True)
    else:
        return (x, False)
def chmax(x, y):
    """change maximum
    if x < y, x = y and return (x, True).
    convenient when solving problems of dp[i]
    
    Args:
        x (long): current maximum value
        y (long): potential maximum value
    
    Returns:
        (x, bool): (x, True) when updated, else (x, False)
    """
    if x < y:
        x = y
        return (x, True)
    else:
        return (x, False)

from fractions import gcd 
def gcds(numbers):
    return reduce(gcd, numbers)
def lcm(x, y):
    return (x * y) // gcd(x, y)
def lcms(numbers):
    return reduce(lcm, numbers, 1)



INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) 
def modinv(a, p = MOD):
    
    
    return modpow(a, p-2, p)
def modinv_list(n, p = MOD):
    if n <= 1:
        return [0,1][:n+1]
    else:
        inv_t = [0,1]
        for i in range(2, n+1):
            inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
        return inv_t
def modfactorial_list(n, p = MOD):
    if n == 0:
        return [1]
    else:
        l = [0] * (n+1)
        tmp = 1
        for i in range(1, n+1):
            tmp = tmp * i % p
            l[i] = tmp
        return l
def modcomb(n, k, fac_list = [], p = MOD):
    
    
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    if len(fac_list) <= n:
        a = factorial(n) % p
        b = factorial(k) % p
        c = factorial(n-k) % p
    else:
        a = fac_list[n]
        b = fac_list[k]
        c = fac_list[n-k]
    return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
def modadd(a, b, p = MOD):
    return (a + b) % MOD
def modsub(a, b, p = MOD):
    return (a - b) % p
def modmul(a, b, p = MOD):
    return ((a % p) * (b % p)) % p
def moddiv(a, b, p = MOD):
    return modmul(a, modpow(b, p-2, p))

""" initialize variables and set inputs

    
    

    
    
    
    
    

    
    
    
    

    
    
"""


r = lambda: sys.stdin.readline().strip()
r_int = lambda: int(r())
R = lambda: list(map(int, r().split()))
Rfloat = lambda: list(map(float, r().split()))
Rtuple = lambda: tuple(map(int, r().split()))
Rmap = lambda: map(int, r().split())

""" how to treat input







"""



N, X = R()
BLU = [R() for _ in range(N)]
BLUV = [(b, l, u, (b*l)+(X-b)*u) for (b, l, u) in BLU]
BLUV.sort(key=itemgetter(3), reverse=True)
Score_Aoki = sum([a*b for (a, b, _) in BLU])
AcV = list(accumulate([i for i in zip(*BLUV)][3]))

Ans = INF
BaseLeft = bisect_left(AcV, Score_Aoki)
for i, (b, l, u, v) in enumerate(BLUV):
    BR1 = BaseLeft
    BR2 = bisect_left(AcV, Score_Aoki + v)
    Remain = Score_Aoki
    Adjust = 0
    if i < BR1:
        BR1 = BR2
        Adjust = 1
        Remain += v
    if BR1 > 0:
        Remain -= AcV[BR1-1]

    if Remain > v:
        continue
    elif Remain >= b*l:
        Ans, _ = chmin(Ans, ceil((Remain-b*l)/u) + b + (BR1-Adjust)*X)
    else:
        Ans, _ = chmin(Ans, ceil(Remain/l) + (BR1-Adjust)*X)

print(Ans)

"""memo: how to use defaultdict of list

Dic = defaultdict(list)

Dic[x].append(y)

for k, v in Dic.items():
"""

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


class TestObj(object):

    def __init__(self, b, l, u, x):
        self.aokip = b
        self.minval = l
        self.maxval = u
        self.maxp = l * b + u * (x-b)

    def calc_point(self, r, x):
        return self.minval * min(self.aokip, r) + self.maxval * max(0, r - self.aokip)


def judge(tests, cum, n, k, x, thr):
    q = k // x
    r = k % x
    takap = 0

    if q >= n:
        return True

    for i in range(1,n+1):
        if i <= q:
            takap = max(takap, cum[q+1] - tests[i].maxp + tests[i].calc_point(r,x))

        else:
            takap = max(takap, cum[q] + tests[i].calc_point(r,x))

        if takap >= thr:
            return True

    return False


def binary_search(tests, x):
    n = len(tests) - 1

    thr = sum([ti.minval * ti.aokip for ti in tests])

    if thr == 0:
        return 0

    low = 0
    high = 10**18

    cum = []
    for ti in tests:
        if len(cum) > 0:
            cum.append(cum[-1] + ti.maxp)
        else:
            cum.append(0)

    while high - low > 1:
        mid = (high+low) // 2

        if judge(tests, cum, n, mid, x, thr):
            high = mid

        else:
            low = mid

    return high

n, x = li()
tests = []
for _ in range(n):
    b,l,u = li()
    tests.append(TestObj(b,l,u,x))

tests.sort(key=lambda x: x.maxp, reverse=True)
tests = [TestObj(0,0,0,x)] + tests
print(binary_search(tests, x))

Solution (Python):
N, X = map(int, input().split())
blu = [[int(i) for i in input().split()] for _ in range(N)]

b_total = 0
dblu = []
for b, l, u in blu :
    dblu.append((u*X-(u-l)*b, b, l, u))
    b_total += b * l
dblu.sort(reverse=True)

s = [0] * (N + 1)
for i in range(1, N + 1) :
    s[i] = s[i-1] + dblu[i-1][0]

ret = float('inf')

def judge(mid) :
    q = mid // X
    r = mid % X
    for i in range(N) :
        d, b, l, u = dblu[i]

        if q < i :
            tmp = s[q]
        else :
            tmp = s[q+1] - d

        if r < b :
            tmp += r * l
        else :
            tmp += b * l + u * (r - b)

        if tmp >= b_total :
            return True
    return False

left, right = -1, N * X

while right - left > 1 :
    mid = (left + right) // 2
    
    if judge(mid) :
        right = mid
    else :
        left = mid

print(right)

Solution (Python):
import sys
import math
import numpy as np
sys.setrecursionlimit(10**7)

class Task:
    def __repr__(self):
        return str(self.__dict__)

    def time_toget_point(self, p):
        
        if p >= self.max_minus:
            return math.ceil(self.b + (p - self.max_minus)/self.u)
        else:
            return math.ceil(p/self.l)

def solve():
    n, x = map(int, input().split())
    t_list = []
    total_behind = 0 

    for i in range(n):
        t = Task()
        t.b, t.l, t.u = map(int, input().split())
        t.max_minus = t.b * t.l
        t.eff = ((x-t.b)*t.u) + (t.b*t.l) 
        t_list.append(t)
        total_behind += t.max_minus

    
    t_list = sorted(t_list, key=lambda t: t.eff, reverse=True)
    cumsum = list(np.cumsum([t.eff for t in t_list]))

    
    import bisect
    for max_i in range(len(t_list)):
        if cumsum[max_i] > total_behind:
            break

    
    min_time = -1
    for i, t in enumerate(t_list):
        if i <= max_i:
            
            rest_p = total_behind - (cumsum[max_i] - t.eff)
        else:
            
            
            if max_i == 0:
                rest_p = total_behind
            else:
                rest_p = total_behind - cumsum[max_i-1]

        
        time = x * (max_i) + t.time_toget_point(rest_p)

        if min_time == -1 or min_time > time:
            min_time = time
    print(min_time)

solve()

Solution (Python):
import sys
import math
sys.setrecursionlimit(10**7)

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

class Task:
    def __repr__(self):
        return str(self.__dict__)
    def time_toget_point(self, p):
        if p >= self.max_minus:
            return math.ceil(self.b + (p - self.max_minus)/self.u)
        else:
            return math.ceil(p/self.l)

def solve():
    n, x = map(int, input().split())
    t_list = []
    total_behind = 0 

    for i in range(n):
        t = Task()
        t.b, t.l, t.u = map(int, input().split())

        t.max_minus = t.b * t.l 
        t.max_plus = (x-t.b) * t.u 
        t.eff = t.max_plus + t.max_minus 
        t_list.append(t)

        total_behind += t.max_minus
    dprint(total_behind)

    
    import numpy as np
    t_list = sorted(t_list, key=lambda t: t.eff, reverse=True)
    cumsum = list(np.cumsum([t.eff for t in t_list]))
    dprint(t_list)
    dprint(cumsum)

    
    import bisect
    for max_i in range(len(t_list)):
        if cumsum[max_i] > total_behind:
            break
    dprint("max_i:", max_i)

    
    min_time = -1
    for i, t in enumerate(t_list):
        if i <= max_i:
            
            rest_p = total_behind - (cumsum[max_i] - t.eff)

        else:
            
            
            if max_i == 0:
                rest_p = total_behind
            else:
                rest_p = total_behind - cumsum[max_i-1]

        time = x * (max_i) + t.time_toget_point(rest_p)
        dprint(i, rest_p, time, min_time, t)
        if min_time == -1 or min_time > time:
            min_time = time
    print(min_time)

solve()

Solution (Python):
import sys
import math
sys.setrecursionlimit(10**7)

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

class Task:
    def __repr__(self):
        return str(self.__dict__)
    def time_toget_point(self, p):
        if p >= self.max_minus:
            return math.ceil(self.b + (p - self.max_minus)/self.u)
        else:
            return math.ceil(p/self.l)

def solve():
    n, x = map(int, input().split())
    t_list = []
    total_behind = 0 

    for i in range(n):
        t = Task()
        t.b, t.l, t.u = map(int, input().split())

        t.max_minus = t.b * t.l 
        t.max_plus = (x-t.b) * t.u 
        t.eff = t.max_plus + t.max_minus 
        t_list.append(t)

        total_behind += t.max_minus
    dprint(total_behind)

    
    import numpy as np
    t_list = sorted(t_list, key=lambda t: t.eff, reverse=True)
    cumsum = list(np.cumsum([t.eff for t in t_list]))
    dprint(t_list)
    dprint(cumsum)

    
    import bisect
    max_i = bisect.bisect_left(cumsum, total_behind)
    dprint("max_i:", max_i)

    
    min_time = -1
    for i, t in enumerate(t_list):
        if i <= max_i:
            
            rest_p = total_behind - (cumsum[max_i] - t.eff)

        else:
            
            
            if max_i == 0:
                rest_p = total_behind
            else:
                rest_p = total_behind - cumsum[max_i-1]

        time = x * (max_i) + t.time_toget_point(rest_p)
        dprint(i, rest_p, time, min_time, t)
        if min_time == -1 or min_time > time:
            min_time = time
    print(min_time)

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    


solve()

Solution (Python):
from itertools import accumulate
import sys
input = sys.stdin.readline

def solve():
    N, X = map(int, input().split())
    tests = []
    D0 = 0
    for _ in range(N):
        B, L, U = map(int, input().split())
        v = L*B + U*(X-B)
        tests.append((v, B, L, U))
        D0 -= L*B
    tests.sort(reverse=True)
    accVs = list(accumulate([0] + tests, lambda accX, X: accX + X[0]))

    def isOK(k):
        q = k // X
        r = k % X
        accV = accVs[q+1]
        for v, B, L, U in tests[:q]:
            d = D0 + accV - v
            if r <= B:
                d += L*r
            else:
                d += L*B + U*(r-B)
            if d >= 0:
                return True
        accV = accVs[q]
        for v, B, L, U in tests[q:]:
            d = D0 + accV
            if r <= B:
                d += L*r
            else:
                d += L*B + U*(r-B)
            if d >= 0:
                return True
        return False

    ng, ok = -1, N*X
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    return ok


print(solve())