#include <bits/stdc++.h>
#define x first
#define y second
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 1e3+10,M=2e4+10,mod = 998244353;
void solve()
{
    int n,k;
    cin>>n>>k;
    vector<PII>nums(n+1,{0,0});
    vector<int>c(n+1,0),w(n+1,0),f(n+1,0);
    for(int i=1;i<=n;i++)
    {
        cin>>c[i]>>w[i]>>f[i];
        nums[i] = {f[i],i};
    }
    sort(nums.begin()+1,nums.end(),greater<PII>());
    auto get = [&](int a,int b)
    {
        return (a+b-1)/b;
    };
    int ans=0,tot=0;
    for(int i=1;i<=n;i++)
    {
        int x = nums[i].x,y=nums[i].y;
        int cnt = c[y];
        if(w[y]==2) cnt*=2;
        ans+=(get(tot+cnt,k)-get(tot,k))*x;
        tot = (tot+cnt)%k;
    }
    cout<<ans<<"\n";
}



signed main()
{
    int T=1;
    cin.tie(0)->sync_with_stdio(false);
    cin>>T;
    //init();
    while(T--)
    {
        solve();
    }
    return 0;
}