test = int ( input ( ) )

for testtest in range ( test ) :

    n , k = map ( int , input () . split () )
    
    A = []
    
    for i in range ( n ) :
        
        c , w , f = map ( int , input () . split ( ) )
        
        A += [ [c,w,f] ]
    
    A.sort(key = lambda x : x[2] , reverse = True )
    
    B =[]
    
    for i in range ( n ) :
        if A[i][1] == 1 :
            B += [ [A[i][0],A[i][1],A[i][2],i] ]
    
    
    
    ans = 0
    h = 0
    c = k
    p = 0
    
    for i in range ( n ) :

        a = A[i]
        
        if a[0] == 0 :
            continue
        
        if c == 0 :
            ans += h
            h = 0
            c = k
        
        if a[0]*a[1] <= c :
            c -= a[0]*a[1]
            h = max(h,a[2])
            continue

        if c%2 == 1 and a[1] == 2:
            while ( p < len(B) ) :
                if B[p][3] < i : p += 1
                else : break
            
            if p != len ( B ) :
                A[B[p][3]][0] -= 1
            
            c -= 1
        
        if c % 2 == 0 or a[1] == 1 :

            a[0] -= c//a[1]
            ans += max(h,a[2])
            h = 0
            c = k
            
            if a[0]*a[1] <= c :
                c -= a[0]*a[1]
                h = max(h,a[2])
                continue
            
            else :
                v = (a[0]*a[1])//c
                ans += a[2] * v
                a[0] -= ( v * c ) // a[1]
                
                if a[0] == 0 :
                    h = 0
                    c = k
                    continue
                else :
                    c -= a[0]*a[1]
                    h = a[2]
                    continue
    
    if c != k :
        ans += h

    print(ans)