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):
from itertools import accumulate

N, X = map(int, input().split())
BLUs = [tuple(map(int, input().split())) for _ in range(N)]

vs = [(L*B + U*(X-B), i) for i, (B, L, U) in enumerate(BLUs)]
vs.sort(reverse=True)

accV = 0
accVs = [0]
for v, i in vs:
    accV += v
    accVs.append(accV)
D0 = -sum([L*B for B, L, U in BLUs])

def isOK(k):
    q = k // X
    r = k % X
    for odr, (v, i) in enumerate(vs):
        B, L, U = BLUs[i]
        d = D0
        if odr < q:
            d += accVs[q+1] - v
        else:
            d += accVs[q]
        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

print(ok)

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)

    accV = 0
    accVs = [0]
    for v, B, L, U in tests:
        accV += v
        accVs.append(accV)

    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())

Solution (Python):
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

from bisect import bisect_right, bisect_left

def main():
    N, X = LI()
    b_l_u = []
    for i in range(N):
        b_l_u.append(LI())

    sum_of_test = [ (b_l_u_i[1]*b_l_u_i[0]+b_l_u_i[2]*(X-b_l_u_i[0]), i) for i,b_l_u_i in enumerate(b_l_u)]
    sum_of_test.sort(reverse=True)  

    cumsum_of_test = []
    tmp = 0
    for i in sum_of_test:  
        tmp += i[0]
        cumsum_of_test.append(tmp)

    B = sum([l*b for b, l, u in b_l_u])  
    head = bisect_right(cumsum_of_test, B)-1
    cumsum = cumsum_of_test[head]


    take_li = []
    for j, (sum_, i) in enumerate(sum_of_test):  
        
        if j <= head:
            new_head = bisect_right(cumsum_of_test, B+sum_)-1  
            new_cumsum = cumsum_of_test[new_head] - sum_
            left = B - new_cumsum
            take_1 = X * new_head
        else:
            left = B - cumsum
            take_1 = X*(head+1)

        if head==-1:  
            left = B
            take_1 = 0

        b, l, u = b_l_u[i]
        from math import ceil
        if left/l <= b:
            take = ceil(left/l)
        else:
            take = b + ceil((left - b*l)/u)

        if take > X: continue

        take_li.append(take+take_1)

    print(min(take_li))

main()

Solution (Python):
N,X=map(int,input().split())
data=[0]*N
A=[0]*N
zero=0
for i in range(N):
    b,l,u=map(int,input().split())
    zero-=l*b
    data[i]=(b,l,u)
    A[i]=(i,(X-b)*u+b*l)
A.sort(key=lambda x:x[1],reverse=True)
S=[0]*N
idx=[0]*N
for i,a in enumerate(A):
    S[i]=S[i-1]+a[1]
    idx[a[0]]=i
def check(k):
    q=k//X
    r=k-q*X
    for i in range(N):
        b,l,u=data[i]
        if q==0:
            now=zero
        elif idx[i]<q:
            now=zero+S[q]-A[idx[i]][1]
        else:
            now=zero+S[q-1]
        if r<=b:
            now+=r*l
        else:
            now+=(r-b)*u+b*l
        if now>=0:
            return True
    return False
Mincan=N*X
Maxcant=-1
c=(1,2)
while True:
    if Maxcant+1==Mincan:
        ans=Mincan
        break
    x=N*X*c[0]//c[1]
    if check(x):
        if Mincan>x:
            Mincan=x
            c=(c[0]*2-1,c[1]*2)
    else:
        if Maxcant<x:
            Maxcant=x
            c=(c[0]*2+1,c[1]*2)
print(ans)

Solution (Python):
n, x = list(map(int, input().split()))
B = 0
blu = []
s = [0 for i in range(n)]

for i in range(n):
  b, l, u = list(map(int, input().split()))
  blu.append((b, l, u, x*u-b*u+b*l))
  B += b*l
blu.sort(key=lambda x: x[3], reverse=True)

for i in range(n):
  if i==0:
    s[i] = blu[i][3]
  else:
    s[i] = s[i-1] + blu[i][3]

ok = n*x
ng = -1
while ok-ng>1:
  A = 0
  mid = (ok+ng)//2
  k = mid//x
  t = mid%x
  for i in range(n):
    if t<=blu[i][0]:
      rm = t*blu[i][1]
    else:
      rm = t*blu[i][2] - blu[i][0]*(blu[i][2]-blu[i][1])
    if k==0:
      A = max(A, rm)
    elif i<k:
      A = max(A, s[k]-blu[i][3]+rm)
    else:
      A = max(A, s[k-1]+rm)
  if A>=B:
    ok = mid
  else:
    ng = mid

print(ok)

Solution (Python):
import sys,heapq,time
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,x = inm()
blu = []
pt = 0
for i in range(n):
    b,l,u = inm()
    s = u*(x-b) + l*b
    v = s/x
    t = x
    heapq.heappush(blu, (-v,s,t,b,l,u,i))
    pt -= l*b

if pt==0:
    print(0)
    exit()

ans = []
reached = False
sum = 0
while len(blu)>0:
    mv,s,t,b,l,u,r = heapq.heappop(blu)
    nxtpt = pt + s
    ddprint("v {} s {} t {} b {} l {} u {} pt {} nx {} sum {}".format(-mv,s,t,b,l,u,pt,nxtpt,sum))
    if nxtpt < 0:
        ans.append((s,b,l,u))
        pt = nxtpt
        sum += t
        continue
    elif nxtpt == 0: 
        if not reached:
            ans.append((s,b,l,u))
            pt2 = pt + u*x - u*b + l*b
        sum += t
        break
    else:  
        m = pt + l*b
        ddprint("m {}".format(m))
        if m>=0:
            t = (-pt+l-1)//l
        else:
            m = -m
            t = b + (m+u-1)//u
        if not reached:
            ans.append((s,b,l,u))
            pt2 = pt + u*x - u*b + l*b
            reached = True
        s = -pt
        ddprint("s/t {} s {} t {}".format(s/t,s,t))
        heapq.heappush(blu, (-s/t,s,t,b,l,u,-1))

sum2 = x * (len(ans)-1)
for z in ans[:-1]:
    s,b,l,u = z
    pt = pt2 - s
    m = pt + l*b
    if m>=0:
        t = (-pt+l-1)//l
    else:
        t = b+(-m+u-1)//u
    if sum2+t < sum:
        sum = sum2+t
print(sum)

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

items = sorted(items, key=lambda x: -(x[3] - x[4]))


def f(num):
    cnt = num // X
    mod = num % X
    point = 0
    for i in range(cnt):
        point += items[i][3]
    for i in range(cnt, N):
        point += items[i][4]

    if mod == 0:
        if point >= 0:
            return True
        else:
            return False
    else:
        tmp = -float("inf")
        for i in range(N):
            b, l, u, d1, d2 = items[i]
            if mod >= b:
                mul = u * (mod - b)
            else:
                mul = l * (mod - b)

            if i < cnt:
                tmp = max(tmp, point - d1 + mul + items[cnt][3] - items[cnt][4])
            else:
                tmp = max(tmp, point - d2 + mul)
        if tmp >= 0:
            return True
        else:
            return False

ok = N * X + 1
ng = - 1
while (ok - ng) > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
import math
class Test:
    pass
n, x = map(int, input().split())
l = []
lose = 0
for _ in range(n):
    t = Test()
    t.b, t.l, t.u = map(int, input().split())
    t.total = t.b * t.l + (x - t.b) * t.u
    l.append(t)
    lose += t.b * t.l
l = sorted(l, key=lambda t: t.total, reverse=True)

sum_upto_i = 0
for i, ti in enumerate(l):
    sum_upto_i += ti.total
    if sum_upto_i >= lose:
        break

min_needed = x
for j, tj in enumerate(l):
    if j <= i:
        lose_left = lose - (sum_upto_i - tj.total)
    else:
        lose_left = lose - (sum_upto_i - ti.total)
    if tj.b * tj.l < lose_left:
        lose_left -= tj.b * tj.l
        if (x - tj.b) * tj.u < lose_left:
            continue
        else:
            needed = tj.b + math.ceil(lose_left / tj.u)
    else:
        needed = math.ceil(lose_left / tj.l)
    if min_needed > needed:
        min_needed = needed
print(x * i + min_needed)

Solution (Python):
n, x = list(map(int, input().split()))

exms = []
nrm = 0

lines = [map(int, input().split()) for _ in range(n)]

for i, line in enumerate(lines):
    b, l, u = line
    exms.append((u * x - b * (u - l), b, l, u, i))
    nrm += b * l
exms_sorted = sorted(exms, reverse=True)


remain_nrm = nrm

sub_d = -1
i = 0
used = set()
for i, (d, b, l, u, ei) in enumerate(exms_sorted):
    if remain_nrm < d:
        sub_d = d
        break
    remain_nrm -= d
    used.add(ei)

if sub_d == -1:
    print(n * x)
    exit()

base_ans = i * x
base_remain_nrm = remain_nrm

ans = 10 ** 10

for d, b, l, u, i in exms:
    if i in used:
        curr_remain_nrm = base_remain_nrm + d - sub_d
    else:
        curr_remain_nrm = base_remain_nrm

    if curr_remain_nrm <= b * l:
        extra = (curr_remain_nrm - 1) // l + 1
    else:
        extra = (curr_remain_nrm + b * (u - l) - 1) // u + 1
    if extra > x:
        continue
    ans = min(ans, base_ans + extra)

print(ans)

Solution (Python):

from itertools import accumulate
from operator import itemgetter

inf = float('inf')

N, X = map(int, input().split())

bs = []
ls = []
us = []
values = []

loss = 0
for idx in range(N):
    b, l, u = map(int, input().split())
    value = X * u - b * (u - l)

    bs.append(b)
    ls.append(l)
    us.append(u)
    values.append(value)

    loss += b * l

order = [idx for idx, _ in sorted(enumerate(values), key=itemgetter(1), reverse=True)]

pref = [0] + list(accumulate(values[idx] for idx in order))

ans = inf
for it in range(N):
    i = order[it]
    for coeff in ls[i], us[i]:
        low = 0
        high = N
        while low <= high:
            mid = (low + high) >> 1
            cur = loss
            if coeff == us[i]:
                cur += bs[i] * (us[i] - ls[i])
            can_get = pref[mid]
            vals = mid
            if it < mid:
                can_get -= values[i]
                vals -= 1
            can_get += X * coeff
            if can_get >= cur:
                can_get -= X * coeff
                need = 0
                if can_get < cur:
                    need = (cur - can_get + coeff - 1) // coeff
                ans = min(ans, vals * X + need)
            if low == high:
                break
            if can_get >= cur:
                high = mid
            else:
                low = mid + 1
print(ans)

Solution (Python):
import os
import sys

import numpy as np

if os.getenv('LOCAL'):
    sys.stdin = open('_in.txt', 'r')

sys.setrecursionlimit(2147483647)
INF = float('inf')


def bisect_right_callable(fn, x, lo, hi):
    """
    lo から hi-1 のうち、fn の結果が x 以下となる、最も右の値 + 1
    bisect.bisect_right と同じ
    https://docs.python.org/ja/3/library/bisect.html
    :param callable fn:
    :param x:
    :param int lo: 最小値
    :param int hi: 最大値 + 1
    :return: lo <= ret <= hi
    """
    while lo < hi:
        mid = (lo + hi) // 2
        if x < fn(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo


N, X = list(map(int, sys.stdin.readline().split()))
B, L, U = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

B = np.array(B, dtype=int)
L = np.array(L, dtype=int)
U = np.array(U, dtype=int)


target = (B * L).sum()


scores = B * L + (X - B) * U
scores_i = scores.argsort()

scores = scores[scores_i]
scores_cumsum = np.concatenate((scores[::-1].cumsum()[::-1], [0]))
B = B[scores_i]
L = L[scores_i]
U = U[scores_i]


def get_max_score(x):
    

    
    perfects = x // X
    
    half_x = x % X

    border = N - perfects
    ret = []
    if len(B[:border]) > 0:
        
        ret.append(max(
            scores_cumsum[border] +
            np.minimum(half_x, B[:border]) * L[:border] + np.maximum(0, half_x - B[:border]) * U[:border]
        ))
    if len(B[border:]) > 0:
        
        ret.append(max(
            scores_cumsum[border - 1] - scores[border:] +
            np.minimum(half_x, B[border:]) * L[border:] + np.maximum(0, half_x - B[border:]) * U[border:]
        ))
    return max(0, *ret)


ans = bisect_right_callable(get_max_score, target - 1, 0, B.sum())
print(ans)

Solution (Python):
from operator import itemgetter

N, X = map(int, input().split())

score = 0
e = []
for idx in range(N):
    b, l, u = map(int, input().split())
    score -= b * l
    adv = (X - b) * u + b * l
    e.append((b, l, u, adv))

e.sort(key=itemgetter(3), reverse=True)  
c_adv = [0]
for b, l, u, adv in e:
    c_adv.append(c_adv[-1] + adv)


def is_ok(total):
    x_subject_count, remain_score = divmod(total, X)
    if remain_score > 0:
        for remain_subject_index in range(N):
            b, l, u, adv = e[remain_subject_index]
            remain_adv = (remain_score - b) * (u if b <= remain_score else l) + b * l

            if remain_subject_index >= x_subject_count:
                if remain_adv + c_adv[x_subject_count] + score >= 0:
                    return True
            else:
                if remain_adv + c_adv[x_subject_count + 1] - adv + score >= 0:
                    return True
    else:
        if c_adv[x_subject_count] + score >= 0:
            return True
    return False


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


print(binary_search())

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

items = sorted(items, key=lambda x: -(x[3] - x[4]))


def f(num):
    cnt = num // X
    mod = num % X
    point = 0
    for i in range(cnt):
        point += items[i][3]
    for i in range(cnt, N):
        point += items[i][4]

    if mod == 0:
        if point >= 0:
            return True
        else:
            return False
    else:
        tmp = -float("inf")
        for i, tmp2 in enumerate(items):
            b, l, u, d1, d2 = tmp2
            if mod >= b:
                mul = u * (mod - b)
            else:
                mul = l * (mod - b)

            if i < cnt:
                tmp = max(tmp, point - d1 + mul + items[cnt][3] - items[cnt][4])
            else:
                tmp = max(tmp, point - d2 + mul)
        if tmp >= 0:
            return True
        else:
            return False

ok = N * X + 1
ng = - 1
while (ok - ng) > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
import numpy as np

N, X = map(int, input().split())

b = np.empty(N, dtype=int)
l = np.empty(N, dtype=int)
u = np.empty(N, dtype=int)

for n in range(N):
    b[n], l[n], u[n] = map(int, input().split())

c = X * u - b*(u - l)
di = np.argsort(c)[::-1]
c = c[di]
b = b[di]
l = l[di]
u = u[di]
bl = b * l
bsum = bl.sum()


c_cumsum = np.cumsum(c)
c_p = np.searchsorted(c_cumsum, bsum, side='left')

if bsum == c_cumsum[c_p]:
    print((c_p + 1)*X)
    exit(0)

if c_p > 0:
    left = bsum - c_cumsum[c_p - 1]
else:
    left = bsum

left1 = left - c[c_p]
ans1 = np.where(left1 + c[:c_p] <= bl[:c_p], (left1 + c[:c_p] - 1) // l[:c_p] + 1, (left1 + c[:c_p] - bl[:c_p] - 1) // u[:c_p] + b[:c_p] + 1)
ans2 = np.where(left <= bl[c_p:], (left - 1) // l[c_p:] + 1, (left - bl[c_p:] - 1) // u[c_p:] + b[c_p:] + 1)
print(c_p * X + np.concatenate((ans1, ans2)).min())

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

items = sorted(items, key=lambda x: -(x[3] - x[4]))


def f(num):
    cnt = num // X
    mod = num % X
    point = 0
    for i in range(cnt):
        point += items[i][3]
    for i in range(cnt, N):
        point += items[i][4]

    if mod == 0:
        if point >= 0:
            return True
        else:
            return False
    else:
        tmp = -float("inf")
        for i in range(N):
            b, l, u, d1, d2 = items[i]
            if mod >= b:
                mul = u * (mod - b)
            else:
                mul = l * (mod - b)

            if i < cnt:
                tmp = max(tmp, point - d1 + mul + items[cnt][3] - items[cnt][4])
            else:
                tmp = max(tmp, point - d2 + mul)
        if tmp >= 0:
            return True
        else:
            return False

ok = N * X + 1
ng = - 1
while (ok - ng) > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Solution (Python):
import numpy as np

N, X = map(int, input().split())

b = np.empty(N, dtype=int)
l = np.empty(N, dtype=int)
u = np.empty(N, dtype=int)

for n in range(N):
    b[n], l[n], u[n] = map(int, input().split())

c = X * u - b*(u - l)
di = np.argsort(c)[::-1]
c = c[di]
b = b[di]
l = l[di]
u = u[di]
bl = b * l
bsum = bl.sum()


c_cumsum = np.cumsum(c)

c_p = np.searchsorted(c_cumsum, bsum, side='left')

if bsum == c_cumsum[c_p]:
    print((c_p + 1)*X)
    exit(0)

if c_p > 0:
    left = bsum - c_cumsum[c_p - 1]
else:
    left = bsum

ans = np.empty(N, dtype=int)
left1 = left - c[c_p]
ans[:c_p] = np.where(left1 + c[:c_p] <= bl[:c_p], (left1 + c[:c_p] - 1) // l[:c_p] + 1, (left1 + c[:c_p] - bl[:c_p] - 1) // u[:c_p] + b[:c_p] + 1)
ans[c_p:] = np.where(left <= bl[c_p:], (left - 1) // l[c_p:] + 1, (left - bl[c_p:] - 1) // u[c_p:] + b[c_p:] + 1)
ans1 = c_p * X + ans.min()
print(ans1)

Solution (Python):
import sys

n, x = list(map(int, input().split()))
exams = []
norma = 0
for i, line in enumerate(sys.stdin):
    b, l, u = map(int, line.split())
    exams.append((u * x - b * (u - l), b, l, u, i))
    norma += b * l
exams_sorted = sorted(exams, reverse=True)

remain_norma = norma
sub_d = -1
i = 0
used = set()
for i, (d, b, l, u, ei) in enumerate(exams_sorted):
    if remain_norma < d:
        sub_d = d
        break
    remain_norma -= d
    used.add(ei)

if sub_d == -1:
    print(n * x)
    exit()

base_ans = i * x
base_remain_norma = remain_norma

ans = 10 ** 10

for d, b, l, u, i in exams:
    if i in used:
        curr_remain_norma = base_remain_norma + d - sub_d
    else:
        curr_remain_norma = base_remain_norma
    if curr_remain_norma <= b * l:
        extra = (curr_remain_norma - 1) // l + 1
    else:
        extra = (curr_remain_norma + b * (u - l) - 1) // u + 1
    if extra > x:
        continue
    ans = min(ans, base_ans + extra)

print(ans)

Solution (Python):
import sys
from bisect import bisect_left
from itertools import accumulate
from operator import itemgetter

n, x = list(map(int, input().split()))
exams = []
norma = 0
for i, line in enumerate(sys.stdin):
    b, l, u = map(int, line.split())
    exams.append((u * x - b * (u - l), b, l, u, i))
    norma += b * l
exams_sorted = sorted(exams, reverse=True)
exams_acc = list(accumulate(map(itemgetter(0), exams_sorted)))
exams_loc = {i: loc for loc, i in enumerate(map(itemgetter(4), exams_sorted))}




ans = 10 ** 10
base_loc = bisect_left(exams_acc, norma)
base_ans = base_loc * x
base_remain_norma = norma - exams_acc[base_loc - 1] if base_loc > 0 else norma

for d, b, l, u, i in exams:
    exam_loc = exams_loc[i]
    if base_loc <= exam_loc:
        curr_ans = base_ans
        curr_remain_norma = base_remain_norma
    else:
        tmp_norma = norma + d
        tmp_loc = bisect_left(exams_acc, tmp_norma)
        curr_ans = (tmp_loc - 1) * x
        curr_remain_norma = tmp_norma - exams_acc[tmp_loc - 1]
    if curr_remain_norma <= b * l:
        extra = (curr_remain_norma - 1) // l + 1
    else:
        extra = (curr_remain_norma + b * (u - l) - 1) // u + 1
    
    
    
    if extra > x:
        continue
    ans = min(ans, curr_ans + extra)

print(ans)

Solution (Python):
import math
INF = 10**18
n, x = [int(item) for item in input().split()]
blu = [[int(item) for item in input().split()] for _ in range(n)]

s_score_list = []
full_score_list = []
for i, (b, l, u) in enumerate(blu):
    s_score_list.append(b * l)
    full_score_list.append([(x-b) * u + b * l, i])
s_score = sum(s_score_list)
full_score_list.sort(reverse=True)

t_score = 0
full_score_set = set()
for i in range(n):
    full_score_set.add(full_score_list[i][1])
    t_score += full_score_list[i][0]
    if t_score >= s_score:
        last_index = full_score_list[i][1]
        surplus = t_score - s_score
        shortage = s_score - t_score + full_score_list[i][0]
        break


max_reduction = 0
for i, (b, l, u) in enumerate(blu):
    if i in full_score_set:
        if (x-b) * u >= surplus:
            max_reduction = max(max_reduction, int(math.floor(surplus / u)))
        elif (x-b) * u + b * l >= surplus:
            max_reduction = max(max_reduction, (x-b) + int(math.floor((surplus - (x-b)*u) / l)))
ans = x * len(full_score_set) - max_reduction


full_score_set.remove(last_index)
min_promotion = INF
for i, (b, l, u) in enumerate(blu):
    if i in full_score_set:
        continue
    if b*l >= shortage:
        min_promotion = min(min_promotion, int(math.ceil(shortage / l)))
    elif b*l + (x-b)*u >= shortage:
        min_promotion = min(min_promotion, b + int(math.ceil((shortage - b*l) / u)))
ans = min(ans, min_promotion + x * len(full_score_set))
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,x=map(int,input().split())
BLU=[list(map(int,input().split())) for _ in range(n)]
for i in range(n):
    b,l,u=BLU[i]
    BLU[i].append(l*b+u*(x-b))
BLU.sort(key=lambda x: -x[3])
acc=0
Acc=[0]*(n+1)
for i in range(n):
    acc+=BLU[i][3]
    Acc[i+1]=acc
s=sum(-BLU[i][1]*BLU[i][0] for i in range(n))

def judge(k):
    q=k//x; r=k%x
    t=0
    if r==0:
        if Acc[q]+s>=0:
            return True
        return False
    for i in range(n):
        t=score(i,q,r)
        if t+s>=0:
            return True
    return False

def score(a,q,r):
    b,l,u,f=BLU[a]
    if r<=b:
        t=l*r
    else:
        t=l*b+u*(r-b)
    if a<=q-1:
        t+=Acc[q+1]-f
    else:
        t+=Acc[q]
    return t

l=0; r=n*x
if judge(0):
    r=0
while l+1<r:
    k=(l+r)//2
    if judge(k):
        r=k
    else:
        l=k
print(r)

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

N, X = map(int, input().split())

q_array = []
s_array = []

score_needed = 0

for i in range(N):
    b, l, u = map(int, readline().split())
    q_array.append([b, l, u, b * l + (X - b) * u])
    s_array.append(b * l + (X - b) * u)
    score_needed += b * l

q_array = sorted(q_array, key=lambda x: -x[3])
s_array = sorted(s_array, key=lambda x: -x)
sum_array = []
ss = 0
for s in s_array:
    ss += s
    sum_array.append(ss)
ans_min = 0
ans_max = N * X
if score_needed == 0:
    print(0)
    exit()
while ans_max - ans_min > 1:
    ans = (ans_min + ans_max) // 2
    use_all = ans // X
    use_part = ans % X
    
    score_get_max = 0
    score_tmp = 0
    if use_part == 0:
        score_get_max = sum_array[use_all - 1]
    else:
        score_get_max = 0
        score_tmp = 0
        for q in q_array:
            b, l, u, s = q
            score_tmp = 0
            if use_part <= b:
                score_tmp = use_part * l
            else:
                score_tmp = (b * l + (use_part - b) * u)
            if use_all > 0:
                if s_array[use_all - 1] <= s:
                    score_tmp += (sum_array[use_all] - s)
                else:
                    score_tmp += sum_array[use_all - 1]
            score_get_max = max(score_get_max, score_tmp)
    
    if score_get_max >= score_needed:
        ans_max = ans
    else:
        ans_min = ans

print(ans_max)

Solution (Python):
n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
t.sort(key=lambda x:(x[1]*x[0] + x[2]*(m-x[0])), reverse=True)
full = [x[1]*x[0] + x[2]*(m-x[0]) for x in t]
cum = [0]
for i in range(n):
	cum.append(cum[-1] + full[i])
aoki = sum([p[0]*p[1] for p in t])
ans = n*m
for i in range(n):
	ok, ng = n*m, -1
	while ok-ng > 1:
		x = (ok+ng) // 2
		res = cum[x//m]
		if (x//m)-1 >= i:
			res -= full[i]
			res += full[x//m]
		res += t[i][1] * min(t[i][0], x%m) + t[i][2] * max(0, (x%m) - t[i][0])
		if res >= aoki:
			ok = x
		else:
			ng = x
	ans = min(ans, ok)
print(ans)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
t.sort(key=lambda x:(x[1]*x[0] + x[2]*(m-x[0])), reverse=True)
full = [x[1]*x[0] + x[2]*(m-x[0]) for x in t]
cum = [0]
for i in range(n):
	cum.append(cum[-1] + full[i])
aoki = sum([p[0]*p[1] for p in t])
ans = n*m
for i in range(n):
	ok, ng = n*m, -1
	while ok-ng > 1:
		x = (ok+ng) // 2
		res = cum[x//m]
		if (x//m)-1 >= i:
			res -= full[i]
			res += full[x//m]
		res += t[i][1] * min(t[i][0], x%m) + t[i][2] * max(0, (x%m) - t[i][0])
		if res >= aoki:
			ok = x
		else:
			ng = x
	ans = min(ans, ok)
print(ans)

Solution (Python):
from itertools import accumulate,chain



def max_merit(b,l,u):
    return u*(X-b) + l*b

def merit(a,b,l,u):
    return (u if a > b else l)*(a-b) + l*b

N,X = map(int,input().split())

blu = list(tuple(map(int,input().split())) for _ in range(N))
required = sum(l*b for b,l,u in blu)
blu = sorted(((max_merit(*x), x) for x in blu), reverse=True)


for mi,x in enumerate(accumulate(m for m,_ in blu)):
    if x >= required:
        msum2 = x
        msum1 = x - blu[mi][0]
        break

def helper():
    for i,(m,x) in enumerate(blu):
        if i >= mi:
            r = required - msum1
        else:
            r = required + m - msum2

        b,l,u = x
        if r <= l*b:
            yield mi*X + (r-1)//l + 1
        else:
            r -= l*b
            yield mi*X + b + (r-1)//u + 1

print(min(helper()))

Solution (Python):
import math

def main():
    buf = input()
    buflist = buf.split()
    N = int(buflist[0])
    X = int(buflist[1])
    iblu = []
    for i in range(N):
        buf = input()
        buflist = buf.split()
        iblu.append((i, int(buflist[0]), int(buflist[1]), int(buflist[2])))
    aoki_score = 0
    takahashi_score = 0
    for x in iblu:
        aoki_score += x[1] * x[2]
    score_gain = []
    for x in iblu:
        score_gain.append((x[0], X * x[3] - x[1] * (x[3] - x[2])))
    score_gain.sort(reverse=True, key=lambda x: x[1])
    study_hour = 0
    for i, x in enumerate(score_gain):
        new_takahashi_score = takahashi_score + x[1]
        if new_takahashi_score < aoki_score:
            study_hour += X
            takahashi_score = new_takahashi_score
        else: 
            score_needed = aoki_score - takahashi_score
            study_minimum = X
            for j in range(i, N):
                penalty = iblu[score_gain[j][0]][1] * (iblu[score_gain[j][0]][3] - iblu[score_gain[j][0]][2])
                st = min(math.ceil(score_needed / iblu[score_gain[j][0]][2]), math.ceil((score_needed + penalty) / iblu[score_gain[j][0]][3]))
                if st < study_minimum:
                    study_minimum = st
            for j in range(i):
                score_needed = aoki_score - new_takahashi_score + score_gain[j][1]
                penalty = iblu[score_gain[j][0]][1] * (iblu[score_gain[j][0]][3] - iblu[score_gain[j][0]][2])
                st = min(math.ceil(score_needed / iblu[score_gain[j][0]][2]), math.ceil((score_needed + penalty) / iblu[score_gain[j][0]][3]))
                if st < study_minimum:
                    study_minimum = st
            
            
            
            study_hour += study_minimum
            takahashi_score = new_takahashi_score
        if takahashi_score >= aoki_score:
            break
    print(study_hour)


if __name__ == '__main__':
    main()

Solution (Python):
N,X = map(int,input().split())
BLU = [list(map(int,input().split())) for i in range(N)]
for i in range(N):
    b,l,u = BLU[i]
    BLU[i].append(u*X-(u-l)*b)
BLU.sort(key = lambda x:-x[3])

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

ans = 0
for i in range(N):
    b,l,u,m = BLU[i]
    if s+m > 0:
        break
    s += m
    ans += X

from math import ceil
def solve(b,l,u,s):
    if u*X-(u-l)*b < s:
        return X
    if l*b >= s:
        return ceil(s/l)
    else:
        return ceil((s+b*(u-l))/u)

h = X
for b,l,u,m in BLU[i:]:
    h = min(h,solve(b,l,u,-s))

for b,l,u,m in BLU[:i]:
    h = min(h,solve(b,l,u,-s-BLU[i][3]+m))

ans += h
print(ans)