#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
typedef long long LL;
#define int long long

inline int read(){
	int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; } 
    while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } 
    return x * f ;
}

const int maxn = 1e5+20;
int n,k;
struct Node{
    int x,y,z;
    bool operator <(const Node X)const{
        return z > X.z;
    }
}A[maxn];

void solve(){
    n = read();k = read();
    for(int i=1;i<=n;i++){
        int a = read(),b = read(),c = read();
        A[i] = (Node){a,b,c};
    }
    sort(A+1,A+1+n);
    LL Ans = 0,res = k,tg = 0;
    for(int i=1;i<=n;i++){
        if(A[i].y==1){
            int t = min(A[i].x,tg);
            A[i].x -= t;
            tg -= t;
        }
        if(res){
            if(res==k) Ans += A[i].z;
            int t = min(res / A[i].y,A[i].x);
            res -= t * A[i].y;
            A[i].x -= t;
            if(A[i].x==0){
                if(res==0) res = k;
                else if(res==1){
                    tg++;
                    res = k;
                }
                else ;
            }
            else{
                if(res==0) res = k;
                else if(res==1){
                    tg++;
                    res = k;
                }
                int t1 = A[i].x * A[i].y / k;
                int t2 = A[i].x * A[i].y % k;
                Ans += t1 * A[i].z;
                Ans += A[i].z;
                res -= t2;
            }
        }
    }
    printf("%lld\n",Ans);
}

signed main(){
	// freopen("1.txt","r",stdin);
	int T = 1;
	T = read();
	while(T--) solve();
	return 0;
}