#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve(){
    int n, k;
    cin>>n>>k;
    vector<vector<int>> a(n);
    for(int i=0; i<n; i++){
        a[i].resize(3);
        // 0 f 1 c 2 w
        cin>>a[i][1]>>a[i][2]>>a[i][0];
    }
    int odd=0, even=0, now, cnt, yv;
    sort(a.begin(), a.end());
    int ans=0;
    for(int i=n-1; i>=0; i--){
        now=a[i][2]*a[i][1];
        cnt=now/k;
        yv=now%k;
        ans=ans+(cnt)*a[i][0];
        if(yv){
            if(odd&&a[i][2]==1){
                odd=0;
                yv-=1;
            }
            if(yv&&yv>even){
                even=even+k-yv;
                ans+=a[i][0];
            }
            else even-=yv;
        }
    }
    cout<<ans<<"\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}