#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
long long n,k;
long long ans,t,remain,cnt;
void doit(int nownum,int w,int nowt){
    //cout<<nownum<<" "<<w<<" "<<nowt<<" "<<ans<<" "<<remain<<endl;
    if (w==1) { 
         if (remain!=0) {
                if (remain+nownum<k) {
                    remain=remain+nownum;
                   return ;
                }
                if (remain+nownum==k){
                    remain=0;
                    return ;
                }
                nownum-=k-remain;
                ans+=((nownum+k-1)/k)*nowt;
                remain=nownum%k;
                t=nowt;
            }
            else {
                ans+=((nownum+k-1)/k)*nowt;
                remain=nownum%k;
                t=nowt;
            } 
    }
    if (w==2){
        if (remain!=0) {
                if (remain+nownum*2<k) {
                    remain=remain+nownum*2;
                     return ;
                }
                if (remain+nownum*2==k){
                    remain=0;
                     return ;
                }
                nownum-=(k-remain)/2;
                if ((k-remain)%2==1) cnt++;
                ans+=1ll*((nownum+k/2-1)/(k/2))*nowt;
                if (k%2==1) cnt+=1ll*(nownum+k/2+1)/(k/2);
                remain=(nownum%(k/2))*2;
                t=nowt;
            }
            else {
                ans+=((nownum+k/2-1)/(k/2))*nowt;
                if (k%2==1) cnt+=(nownum+k/2+1)/(k/2);
                remain=(nownum%(k/2))*2;
                t=nowt;
            } 
    }
}

void sol(){
    scanf("%lld%lld",&n,&k);
    priority_queue<pair<int,int> >q,p;
    for(int i=1;i<=n;i++){
        int num,w,tt;
        scanf("%lld%lld%lld",&num,&w,&tt);
        if (w==1) q.push(make_pair(tt,num));
        if (w==2) p.push(make_pair(tt,num));
    }
    ans=0,remain=0; cnt=0;
    while(!q.empty()||!p.empty()){
        if (p.empty()){
            int nowt=q.top().first,nownum=q.top().second; q.pop();
            doit(nownum,1,nowt);
        }
        else if (q.empty()){
            int nowt=p.top().first,nownum=p.top().second; p.pop();
            doit(nownum,2,nowt);
        }
        else {
           int nowt=q.top().first,nownum=q.top().second; 
              int nowt1=p.top().first,nownum1=p.top().second;
             if (nowt>=nowt1) {
                q.pop();
                 doit(nownum,1,nowt);
             }
             else {
                p.pop();
                doit(nownum1,2,nowt1);
             }
        }
        while(cnt){
        	if (q.empty())  cnt=0;
        	else {
        		int nowt=q.top().first,nownum=q.top().second; q.pop();
        		if (cnt>=nownum){
        			cnt-=nownum;
				}
				else {
					nownum-=cnt;
					q.push(make_pair(nowt,nownum));
					cnt=0;
				}
			}
		}
        //cout<<ans<<" "<<remain<<endl;
    }
    cout<<ans<<endl;
}

signed main() {
//   freopen("input.in","r",stdin);
//   freopen("output.out","w",stdout);
  int z; cin >> z;
  while (z--) {
    sol();
  }
  
  return 0;
}