#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve(){
    ll n, k;
    cin >> n >> k;
    priority_queue<pair<ll, ll>> q1, q2;
    for(int i = 1;i <= n;i++){
        ll c, w, f;
        cin >> c >> w >> f;
        if(w == 1) q1.push({f, c});
        else if(w == 2) q2.push({f, c});
    }
    ll ans = 0;
    while(q1.size() || q2.size()){
        ll w = 0;
        ll f = 0;
        if(q1.size() && (q1.top().first > q2.top().first || q2.size() == 0)){
            auto now = q1.top();
            if(now.second > k){
                q1.pop();
                ll x = now.second / k;
                ans += x * now.first;
                now.second %= k;
                if(now.second > 0) q1.push(now);
                continue;
            }
        }
        else if(q2.size()){
            auto now = q2.top();
            if(now.second * 2 > k){
                q2.pop();
                ll x = now.second * 2 / k;
                ans += x * now.first;
                now.second %= k/2;
                if(now.second > 0) q2.push(now);
                continue;
            }
        }
        while(w < k && (q1.size() || q2.size())){
            if(q1.size() && (k - w == 1 || q2.size() == 0 || q1.top().first > q2.top().first)){
                auto now = q1.top();
                q1.pop();
                f = max(f, now.first);
                ll x = min(k - w, now.second);
                w += x;
                now.second -= x;
                if(now.second > 0) q1.push(now);
            }
            else if(k - w > 1 && q2.size()){
                auto now = q2.top();
                q2.pop();
                f = max(f, now.first);
                ll x = (k - w) / 2;
                w += min(x, now.second) * 2;
                now.second -= x;
                if(now.second > 0) q2.push(now);
            }
            else break;

        }
        ans += f;
    }
    cout << ans << '\n';
}

int main(){
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}