It's another Start[c]up finals, and that means there is pizza to order for the onsite contestants. There are only 2 types of pizza (obviously not, but let's just pretend for the sake of the problem), and all pizzas contain exactly S slices.

It is known that the i-th contestant will eat s_{i} slices of pizza, and gain a_{i} happiness for each slice of type 1 pizza they eat, and b_{i} happiness for each slice of type 2 pizza they eat. We can order any number of type 1 and type 2 pizzas, but we want to buy the minimum possible number of pizzas for all of the contestants to be able to eat their required number of slices. Given that restriction, what is the maximum possible total happiness that can be achieved?


-----Input-----

The first line of input will contain integers N and S (1 ≤ N ≤ 10^5, 1 ≤ S ≤ 10^5), the number of contestants and the number of slices per pizza, respectively. N lines follow.

The i-th such line contains integers s_{i}, a_{i}, and b_{i} (1 ≤ s_{i} ≤ 10^5, 1 ≤ a_{i} ≤ 10^5, 1 ≤ b_{i} ≤ 10^5), the number of slices the i-th contestant will eat, the happiness they will gain from each type 1 slice they eat, and the happiness they will gain from each type 2 slice they eat, respectively.


-----Output-----

Print the maximum total happiness that can be achieved.


-----Examples-----
Input
3 12
3 5 7
4 6 7
5 9 5

Output
84

Input
6 10
7 4 7
5 8 8
12 5 8
6 11 6
3 3 7
5 9 6

Output
314



-----Note-----

In the first example, you only need to buy one pizza. If you buy a type 1 pizza, the total happiness will be 3·5 + 4·6 + 5·9 = 84, and if you buy a type 2 pizza, the total happiness will be 3·7 + 4·7 + 5·5 = 74.

Difficulty: interview

Starter code:

Solutions:

def bins(sortedlist,x):
    n=len(sortedlist)
    start = 0
    end = n - 1

    while(start <= end):
        mid =int( (start + end)/2)
        if (x == sortedlist[mid][0]):
            return mid
        elif(x < sortedlist[mid][0]):
            end = mid - 1
        else:
            start = mid + 1 
 
    if(sortedlist[mid][0]<=x):
        return mid
    else:
        return mid-1




n,s=list(map(int,input().split()))
hap=[]

for i in range(n):
    hap.append(list(map(int,input().split())))
a=0
max1=0
b=0
sla=[]
slb=[]
slab=[]
for i in range(n):
    temp=hap[i][0]
    hap[i][0]=hap[i][1]
    hap[i][1]=hap[i][2]
    hap[i][2]=temp
for i in range(n):

    slab.append([hap[i][0]-hap[i][1],hap[i][2]])
happi=0
for i in range(n):
    if(hap[i][0]>hap[i][1]):
        a+=hap[i][2]
        happi+=hap[i][2]*hap[i][0]
    else:
        b+=hap[i][2]
        happi+=hap[i][2]*hap[i][1]
sla.sort()
slb.sort()
slab.sort()
if((a%s +  b%s)>s):
    print(happi)
else:
    loc=bins(slab,0)
    happia=happi
    count=0
    #print(a,b)
    b=b%s
    a=a%s
    left=b%s
    
    while(left>0):
        if(slab[loc+count][1]<left):
            happia+=slab[loc+count][0]*slab[loc+count][1]
            left-=slab[loc+count][1]
        else:
            happia+=slab[loc+count][0]*left
            break
        count-=1
    left=a%s
    count=0
    happib=happi
    
    while(loc<n and slab[loc][0]<=0):
        loc+=1
    #print(slab[loc][0])
    while(left>0):
        if(slab[loc+count][1]<left):
            happib-=slab[loc+count][0]*slab[loc+count][1]
            left-=slab[loc+count][1]
        else:
            happib-=slab[loc+count][0]*left
            break
        count+=1
    #print(happia,happib,happi)
    print(max(happia,happib))  


from collections import namedtuple


Member = namedtuple('Member', ['parts', 'a_happy', 'b_happy'])


def happy_diff(m):
    return m.a_happy - m.b_happy


def main():
    input_strings_members, parts = read_input()
    a_members, b_members, other_members = prepare_members(input_strings_members)
    print(count_parts(a_members, b_members, other_members, parts))


def read_input():
    counts_str = input().split()
    members_count, parts = list(map(int, counts_str))
    return [input() for _ in range(members_count)], parts


def prepare_members(input_strings_members):
    a_members = []
    b_members = []
    other_members = []
    for line in input_strings_members:
        m = Member(*list(map(int, line.split())))
        if happy_diff(m) > 0:
            a_members.append(m)
        elif happy_diff(m) < 0:
            b_members.append(m)
        else:
            other_members.append(m)
    return a_members, b_members, other_members


def count_parts(a_members, b_members, other_members, parts_in_one):
    a_members.sort(key=lambda m: happy_diff(m), reverse=False)
    a_modulo = sum(m.parts for m in a_members) % parts_in_one

    a_modulo_members, a_happy_members = split_members_into_happy_groups(a_members, a_modulo)
    a_happy = sum(m.a_happy * m.parts for m in a_happy_members)

    b_members.sort(key=lambda m: happy_diff(m), reverse=True)
    b_modulo = sum(m.parts for m in b_members) % parts_in_one

    b_modulo_members, b_happy_members = split_members_into_happy_groups(b_members, b_modulo)
    b_happy = sum(m.b_happy * m.parts for m in b_happy_members)

    last_happy = count_last_pizzas_happy(a_modulo_members, b_modulo_members, other_members, parts_in_one)

    return a_happy + b_happy + last_happy


def split_members_into_happy_groups(members, modulo):
    modulo_members = []
    happy_members = []
    current_modulo = 0

    for i in range(len(members)):
        m = members[i]
        new_current_modulo = current_modulo + m.parts
        if new_current_modulo < modulo:
            modulo_members.append(m)
            current_modulo = new_current_modulo
            continue

        modulo_members.append(Member(modulo - current_modulo, m.a_happy, m.b_happy))
        if new_current_modulo > modulo:
            happy_members.append(Member(new_current_modulo - modulo, m.a_happy, m.b_happy))
        if (i + 1) < len(members):
            happy_members.extend(members[(i + 1):])
        break

    return modulo_members, happy_members


def count_last_pizzas_happy(a, b, other, parts_in_one):
    last_sorted_members = a + other + b

    if sum(m.parts for m in last_sorted_members) <= parts_in_one:
        return max(
            sum(m.a_happy * m.parts for m in last_sorted_members),
            sum(m.b_happy * m.parts for m in last_sorted_members)
        )

    return sum(m.a_happy * m.parts for m in a + other) + sum(m.b_happy * m.parts for m in b)


def test1():
    a, b, c = prepare_members(['7 4 7', '5 8 8', '12 5 8', '6 11 6', '3 3 7', '5 9 6'])
    assert count_parts(a, b, c, 10) == 314


def test2():
    a, b, c = prepare_members(['3 5 7', '4 6 7', '5 9 5'])
    assert count_parts(a, b, c, 12) == 84


def test3():
    a, b, c = prepare_members(['2 3 1', '2 2 2', '2 1 3'])
    assert count_parts(a, b, c, 3) == 16


def test4():
    a, b, c = prepare_members(
        [
            '2 1 4',
            '2 3 1',
        ]
    )
    assert count_parts(a, b, c, 3) == 14


def test5():
    a, b, c = prepare_members(
        [
            '2 1 2',
            '2 2 1',
            '2 1 3',
            '2 3 1',
            '2 1 4',
            '2 4 1',
        ]
    )
    assert count_parts(a, b, c, 3) == (8 + 6 + 4) * 2


def test6():
    a, b, c = prepare_members(
        [
            '2 1 2',
            '2 2 1',
            '2 1 3',
            '2 3 1',
            '2 1 4',
            '2 4 1',
        ]
    )
    assert count_parts(a, b, c, 5) == 16 + 16 + 3


def test_without_last_pizzas():
    a, b, c = prepare_members(
        [
            '3 3 1',
            '3 5 6'
        ]
    )
    assert count_parts(a, b, c, 3) == 27


def test_with_one_last_pizza():
    a, b, c = prepare_members(
        [
            '2 3 1',
            '1 5 6'
        ]
    )
    assert count_parts(a, b, c, 3) == 11


def test_with_two_last_pizzas():
    a, b, c = prepare_members(
        [
            '2 3 4',
            '2 3 1',
            '1 1 1'
        ]
    )
    assert count_parts(a, b, c, 3) == 15


def test_without_different_happies():
    a, b, c = prepare_members(
        [
            '2 2 2',
            '4 1 1',
            '5 6 6'
        ]
    )
    assert count_parts(a, b, c, 3) == 38


def __starting_point():
    main()

__starting_point()

def solve(ls):

    ls.sort(key=lambda q: q[1] - q[0])

    m = sum(si for a, b, si in ls)

    k = s * (m // s)

    n = m - k

    x = y = z = 0

    for a, b, si in ls:

        if k >= si:

            k -= si

            z += si * a

        elif k:

            z += k * a

            x = (si - k) * a

            y = (si - k) * b

            k = 0

        else:

            x += si * a

            y += si * b

    return x, y, z, n



n,s = list(map(int,input().split()))

first=[]

second=[]

for i in range(n):

	si, ai, bi = list(map(int,input().split()))

	if ai>bi:

		first.append((ai,bi,si))

	else:

		second.append((bi,ai,si))

x1,y1,z1,n1 = solve(first)

x2,y2,z2,n2 = solve(second)

d = x1+x2 if n1+n2>s else max(x1+y2,x2+y1)

print(z1+z2+d)





# Made By Mostafa_Khaled


from sys import stdin
from collections import deque

n,S = [int(x) for x in stdin.readline().split()]

ppl = []

base = 0

tSlices = 0

for dude in range(n):
    s,a,b = [int(x) for x in stdin.readline().split()]
    base += s*a
    tSlices += s
    ppl.append([b-a,s])
#print(base)

if tSlices % S != 0:
    ppl.append([0, S-(tSlices%S)])

ppl.sort(reverse=True)

totalS = 0
totalH = 0

for h,s in ppl:
    if totalS + s < S:
        totalS += s
        totalH += h*s
    else:
        s -= S-totalS
        totalH += h*(S-totalS)
        if totalH > 0:
            base += totalH
        else:
            break
        totalS = 0
        totalH = 0
        if h > 0:
            base += h*((s//S)*S)
            totalS = s%S
            totalH = h*(s%S)
        else:
            break
        
    
print(base)