#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();
    // if(5501 - N==39) cout<<n<<" "<<k<<" ";
    for(int i=1;i<=n;i++){
        int a = read(),b = read(),c = read();
        A[i] = (Node){a,b,c};
    // if(5501 - N==39) cout<<a<<" "<<b<<" "<<" "<<c<<" ";
    }
    sort(A+1,A+1+n);
    LL Ans = 0,res = 0,tg = 0;
    for(int i=1;i<=n;i++){
        // cout<<A[i].x<<" "<<A[i].y<<" "<<A[i].z<<endl;
        if(A[i].y==1){
            int t = min(A[i].x,tg);
            A[i].x -= t;
            tg -= t;
        }
        if(A[i].x){
            if(res==0){
                Ans += A[i].z;
                res = k;
            }
            else if(res==1&&A[i].y==2){
                Ans += A[i].z;
                res = k;
                tg++;
            }
            int t = min(res / A[i].y,A[i].x);
            res -= t * A[i].y;
            A[i].x -= t;
            if(A[i].x==0){
            }
            else{
                int t1 = A[i].x * A[i].y / k;
                int t2 = A[i].x * A[i].y % k;
                Ans += t1 * A[i].z;
                // if(t2) Ans += A[i].z;
                // res -= t2;
                if(t2){
                    if(res==1) tg++;
                    res = k - t2;
                    Ans += A[i].z;
                }
            }
        }
        // cout<<Ans<<endl;
    }
    printf("%lld\n",Ans);
}

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