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

int c[100010],w[100010],f[100010];
vector<pair<int,int>>odd,even;
void solve(){
  odd.clear(),even.clear();
  int n,k;cin>>n>>k;
  for(int i=1;i<=n;++i){
    cin>>c[i]>>w[i]>>f[i];
    if(w[i]==2)even.emplace_back(-f[i],c[i]);
    else{
      if(c[i]%2==0)even.emplace_back(-f[i],c[i]/2);
      else if(c[i]==1)odd.emplace_back(-f[i],c[i]);
      else even.emplace_back(-f[i],c[i]/2),odd.emplace_back(-f[i],1);
    }
  }
  sort(odd.begin(),odd.end());
  int len=odd.size();
  for(int i=0;i<len;i+=2)even.emplace_back(odd[i].first,1);
  sort(even.begin(),even.end());
  len=even.size();k/=2;
  int ans=0,rest=0;
  for(int i=0;i<len;++i){
    if(even[i].second<=rest){rest-=even[i].second;continue;}
    else even[i].second-=rest,rest=0;
    ans+=even[i].second/k*(-even[i].first);
    if(even[i].second%k)ans-=even[i].first;
    rest=(k-even[i].second%k)%k;
  }
  cout<<ans<<endl;
}
signed main(){
  int t;cin>>t;
  while(t--)solve();
  return 0;
}