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



Sample input:
2 100
85 2 3
60 1 1


Sample output:
115

Submission status: Wrong Answer

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

""" convenient functions
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
# accumulate() returns iterator! to get list: list(accumulate())
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 = []  # prime factor
    b, e = 2, 0  # base, exponent
    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
    """
    # TODO: How should I do when n - r is negative?
    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 # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
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 # Deprecated since version 3.5: Use math.gcd() instead.
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)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    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):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    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
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    # flat = [flatten for inner in data for flatten in inner]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
"""

# functions used
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
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]
"""

# set inputs
# sys.stdin = open('sample.txt') # for test
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
    if i < BR1:
        BR1 = BR2
        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*X)
    else:
        Ans, _ = chmin(Ans, ceil(Remain/l) + BR1*X)

print(Ans)

"""memo: how to use defaultdict of list
# initialize
Dic = defaultdict(list)
# append
Dic[x].append(y)
# for
for k, v in Dic.items():
"""


# if __name__ == '__main__':
#     main()

Submission status: Wrong Answer

Solution code:
# using main() makes code faster from the point of view of "access to variables in global name-space"
# def main():

""" convenient functions
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
"""

import sys
sys.setrecursionlimit(10**7)
from itertools import accumulate, combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
# accumulate() returns iterator! to get list: list(accumulate())
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 = []  # prime factor
    b, e = 2, 0  # base, exponent
    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
    """
    # TODO: How should I do when n - r is negative?
    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 # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from operator import itemgetter
# ex1: List.sort(key=itemgetter(1))
# ex2: sorted(tuples, key=itemgetter(1,2))
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 # Deprecated since version 3.5: Use math.gcd() instead.
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)

# first create factorial_list
# fac_list = mod_factorial_list(n)
INF = 10 ** 18
MOD = 10 ** 9 + 7
modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
def modinv(a, p = MOD):
    # evaluate reciprocal using Fermat's little theorem:
    # a**(p-1) is identical to 1 (mod p) when a and p is coprime
    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):
    # fac_list = modfactorial_list(100)
    # print(modcomb(100, 5, modfactorial_list(100)))
    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
# initialize variables
    # to initialize list, use [0] * n
    # to initialize two dimentional array, use [[0] * N for _ in range(N)]
# set inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
# preprocessing
    # transpose = [x for x in zip(*data)]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
    # flat = [flatten for inner in data for flatten in inner]
    # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
# calculate and output
    # output pattern
    # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
"""

# functions used
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
# single int: int(r())
# single string: r()
# single float: float(r())
# line int: R()
# line string: r().split()
# line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
# lines int: [R() for _ in range(n)]
"""

# set inputs
# sys.stdin = open('sample.txt') # for test
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
    if i < BR1:
        BR1 = BR2
        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*100)
    else:
        Ans, _ = chmin(Ans, ceil(Remain/l) + BR1*100)

print(Ans)

"""memo: how to use defaultdict of list
# initialize
Dic = defaultdict(list)
# append
Dic[x].append(y)
# for
for k, v in Dic.items():
"""


# if __name__ == '__main__':
#     main()

Submission status: Wrong Answer

Solution code:
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

    low = 0
    high = 10**18

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

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

Submission status: Wrong Answer

Solution code:
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: int, l: int, u: int, x: int):
        self.maxval = u
        self.minval = l
        self.aoki = b
        self.maxp = l * b + u * (x-b)

    def cum(self, time: int):
        return self.minval * time


def find_max_cum(tests):
    cum = [0]
    for ti in tests:
        cum.append(cum[-1] + ti.maxp)

    return cum


def find_aokip(tests):
    ans = 0
    for ti in tests:
        ans += ti.minval * ti.aoki

    return ans


def takahashiWin(tests, k: int, x: int, max_cum: list, aokip: int):
    n = len(tests)
    maxcnt = k // x
    rest = k % x

    if maxcnt >= n:
        return True

    if max_cum[maxcnt] + tests[maxcnt].cum(rest) >= aokip:
        return True
    else:
        return False


def binary_search(tests: list, x: int):
    low = 0
    high = 10**18 + 1
    max_cum = find_max_cum(tests)
    aokip = find_aokip(tests)

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

        if takahashiWin(tests, mid, x, max_cum, aokip):
            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)

ans = binary_search(tests, x)

print(ans)

Submission status: Wrong Answer

Solution code:
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: int, l: int, u: int, x: int):
        self.maxval = u
        self.minval = l
        self.aoki = b
        self.maxp = l * b + u * (x-b)

    def cum(self, time: int):
        return self.minval * min(self.aoki, time) + self.maxval * max(0, time - self.aoki)


def find_max_cum(tests):
    cum = [0]
    for ti in tests:
        cum.append(cum[-1] + ti.maxp)

    return cum


def find_aokip(tests):
    ans = 0
    for ti in tests:
        ans += ti.minval * ti.aoki

    return ans


def takahashiWin(tests, k: int, x: int, max_cum: list, aokip: int):
    n = len(tests)
    maxcnt = k // x
    rest = k % x

    if maxcnt >= n:
        return True

    if max_cum[maxcnt] + tests[maxcnt].cum(rest) >= aokip:
        return True
    else:
        return False


def binary_search(tests: list, x: int):
    low = 0
    high = 10**18 + 1
    max_cum = find_max_cum(tests)
    aokip = find_aokip(tests)

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

        if takahashiWin(tests, mid, x, max_cum, aokip):
            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)

ans = binary_search(tests, x)

print(ans)

Submission status: Wrong Answer

Solution code:
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: int, l: int, u: int, x: int):
        self.maxval = u
        self.minval = l
        self.aoki = b
        self.maxp = l * b + u * (x-b)

    def cum(self, time: int):
        return self.minval * min(self.aoki, time) + self.maxval * max(0, time - self.aoki)


def find_max_cum(tests):
    cum = [0]
    for ti in tests:
        cum.append(cum[-1] + ti.maxp)

    return cum


def find_aokip(tests):
    ans = 0
    for ti in tests:
        ans += ti.minval * ti.aoki

    return ans


def takahashiWin(tests, k: int, x: int, max_cum: list, aokip: int):
    n = len(tests)
    maxcnt = k // x
    rest = k % x

    if maxcnt >= n:
        return True

    if max_cum[maxcnt] + tests[maxcnt].cum(rest) >= aokip:
        return True
    else:
        return False


def binary_search(tests: list, x: int):
    low = 0
    high = 10**18 + 1
    max_cum = find_max_cum(tests)
    aokip = find_aokip(tests)

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

        if takahashiWin(tests, mid, x, max_cum, aokip):
            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)
for ti in tests:
    print(ti.maxp)

ans = binary_search(tests, x)

print(ans)

Submission status: Wrong Answer

Solution code:
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: int, l: int, u: int, x: int):
        self.maxval = u
        self.minval = l
        self.aoki = b
        self.maxp = l * b + u * (x-b)

    def cum(self, time: int):
        return self.minval * min(self.aoki, time) + self.maxval * max(0, time - self.aoki)


def find_max_cum(tests):
    cum = [0]
    for ti in tests:
        cum.append(cum[-1] + ti.maxp)

    return cum


def find_aokip(tests):
    ans = 0
    for ti in tests:
        ans += ti.minval * ti.aoki

    return ans


def takahashiWin(tests, k: int, x: int, max_cum: list, aokip: int):
    n = len(tests)
    maxcnt = k // x
    rest = k % x

    if maxcnt >= n:
        return True

    if max_cum[maxcnt] + tests[maxcnt].cum(rest) >= aokip:
        return True
    else:
        return False


def binary_search(tests: list, x: int):
    low = 0
    high = 10**10 + 1
    max_cum = find_max_cum(tests)
    aokip = find_aokip(tests)

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

        if takahashiWin(tests, mid, x, max_cum, aokip):
            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)

ans = binary_search(tests, x)

print(ans)

Submission status: Wrong Answer

Solution code:
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)

i = 0
ret = 0

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 = 0, N * X

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

print(right)

Submission status: Wrong Answer

Solution code:
# for i, a in enumerate(iterable)
# q, mod = divmod(a, b)
# divmod(x, y) returns the tuple (x//y, x%y)
# manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7

from itertools import combinations, permutations # https://docs.python.org/ja/3/library/itertools.html
from math import factorial
def combinations_count(n, r):
    # faster than the following code
    # def combinations_count(n, r):
    #     return factorial(n) // (factorial(n - r) * factorial(r))
    if n - r < r: r = n - r
    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 combination_with_repetition_count(n, r):
    return combinations_count(n + r - 1, r)
from collections import deque, Counter # https://docs.python.org/ja/3/library/collections.html#collections.deque
from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
from functools import reduce
from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
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)

# set the inputs
    # open(0).read() is a convenient method:
    # ex) n, m, *x = map(int, open(0).read().split())
    #     min(x[::2]) - max(x[1::2])
    # ex2) *x, = map(int, open(0).read().split())
    #     don't forget to add comma after *x if only one variable is used
    # R = lambda: list(map(int, input2().split()))
    # old_R = lambda: list(map(int, input().split()))
    # ex1) n, k = R()
    # ex2) v = list(R())
    # ex3) bc = [list(R()) for _ in range(m)]

# n, x =2, 100
# blu = [[85, 2, 3],[60, 1, 1]]

# n, x = 10, 1000
# blu = [[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]]

input2 = sys.stdin.readline
R = lambda: list(map(int, input2().split()))
n, x = R()
blu = [R() for _ in range(n)]

# calculate
tests = [(b * l + (x - b) * u, i) for i, (b, l, u) in enumerate(blu)]
tests.sort(reverse=True)
point_Aoki = sum([b * l for b, l, _ in blu])
point_Taka = 0
ans = 0
for i, test in enumerate(tests):
    if point_Taka + test[0] >= point_Aoki:
        ans += i * x
        num_break_Aoki = test[1]
        break
    point_Taka += test[0]

(b, l, u) = blu[num_break_Aoki]
if point_Taka + b*l >= point_Aoki:
    q, mod = divmod(point_Aoki - point_Taka,l)
    ans += q
    if mod != 0:
        ans += 1
else:
    point_Taka += b * l
    ans += b
    q, mod = divmod(point_Aoki - point_Taka,u)
    ans += q
    if mod != 0:
        ans += 1

# output
# ex1) print(*l) => when l = [2, 5], printed 2 5 6
print(ans)