#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define endl "\n"
using namespace std;
const int max_n=1e5+3;
int x[max_n],y[max_n],a[max_n];

void solve(){
  int n,k;
  cin >> n >> k;
  for(int i=1;i<=n;i++){
    int c,w,f;
    cin >> c >> w >> f;
    a[i]=f;
    if(w==2) x[f]+=c;
    else y[f]+=c;
  }
  sort(a+1,a+1+n);
  int cnt=unique(a+1,a+1+n)-a-1;
  int L=cnt;
  int ans=0;
  int pre=0;
  while(L>=1){
    int l=a[L];
    if(y[l]>=pre){
      y[l]-=pre;
      pre=0;
    }else{
      pre-=y[l];
      y[l]=0;
    }
    if(x[l]==0 && y[l]==0){
      L--;
      continue;
    }
    int res;
    if(2*x[l]+y[l]<=k){
      res=k-2*x[l]-y[l];
      ans+=l;
    }else{
      int tmp=k/2;
      ans+=(x[l]/tmp)*l;
      int tem=2*(x[l]%tmp);
      if(tem==0 && y[l]==0){
        res=0;
      }else{
        ans+=l;
        if(tem+y[l]<=k){
          res=k-tem-y[l];
        }else{
          y[l]-=(k-tem);
          ans+=(y[l]/k)*l;
          if(y[l]%k!=0) ans+=l,res=k-(y[l]%k);
          else res=0;
        }
      }
    }
    for(int I=L-1;I>=1&&res>1;I--){
      int i=a[I];
      if(y[i]>=pre){
        y[i]-=pre;
        pre=0;
      }else{
        pre-=y[i];
        y[i]=0;
      }
      if(x[i]==0 && y[i]==0){
        continue;
      }
        int tmp=res/2;
        if(tmp<=x[i]){
          x[i]-=tmp;
          res=res%2;
        }else{
          res=res%2+2*(tmp-x[i]);
          x[i]=0;
        }
        if(res==0 || y[i]==0){
          continue;
        }else{
          if(y[i]<=res){
            res-=y[i];
            y[i]=0;
          }else{
            y[i]-=res;
            res=0;
          }
        }
    }
    if(res==1) pre++;
    L--;
  }
  for(int i=1;i<=cnt;i++){
    x[a[i]]=y[a[i]]=0;
  }
  cout << ans << endl;
}
signed main(){
  ios::sync_with_stdio(false);cin.tie(0);
  int t=1;
  cin >> t;
  while(t--){
    solve();
  }
}