#include<bits/stdc++.h>
#define int long long
const int N=1e5+10;
using namespace std;
int a[N][3];
signed main(){
    // 
    int T;
    cin>>T;
    while(T--){
        int n, k;
        set<int> num;
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            int c, w, f;
            cin>>c>>w>>f;
            a[f][w]+=c;
            num.insert(f);
        }
        int last=0, ans=0;
        for(auto it=num.rbegin();it!=num.rend();it++){
            int x=*it;
            int tot=a[x][1]+2*a[x][2];
            if(last>=tot){
                last-=tot;
            }
            else{
                tot-=last;
                int cost=(tot-1)/k+1;
                ans+=x*cost;
                last=cost*k-tot;
            }
        }
        for(auto x:num){
            a[x][1]=a[x][2]=0;
        }
        cout<<ans<<'\n';
    }
    return 0;
}