#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
#define PII pair<int,int>
#define int long long
//#define int __int128
using namespace std;
inline int read();
inline void write(int x);
const int N = 5e3 + 10, M = 1e4 + 10, mod = 998244353, inf = 1e18, base = 131;
const double eps = 1e-7;
int n, m, k;
void solve(){
    cin >> n >> k;
    priority_queue<PII> heap1;
    priority_queue<PII> heap2;
    for(int i = 1; i <= n; i++){
        int a, b, c;
        cin >> a >> b >> c;
        if(b == 1){
            heap1.push({c, a});
        }
        else{
            heap2.push({c, a});
        }
    }
    int res = 0;
    int cal = k;
    int maxn = -1;
    int cnt = 0;
    while(heap1.size() || heap2.size()){
        PII a, b;
        if(heap1.size()) a = heap1.top();
        else a = {-inf, 1};
        if(heap2.size()) b = heap2.top();
        else b = {-inf, 1};
        if(a.first > b.first){
            if(heap1.size()) heap1.pop();
            maxn = max(maxn, a.first);
            if(a.second > cnt){
                a.second -= cnt;
                cnt = 0;
            }
            else{
                cnt -= a.second;
                continue;
            }
            if(a.second == cal){
                res += maxn;
                cal = k;
                maxn = -1;
            }
            else if(a.second > cal){
                a.second -= cal;
                res += maxn;
                maxn = a.first;
                res += maxn * (a.second / k);
                cal = k - (a.second % k);
                if(cal == k){
                    maxn = -1;
                }
            }
            else{
                cal = cal - a.second;
            }
        }
        else{
            if(heap2.size())heap2.pop();
            maxn = max(maxn, b.first);
            if(2 * b.second == cal){
                //cout << "111" << endl;
                res += maxn;
                cal = k;
                maxn = -1;
            }
            else if(2 * b.second > cal){
                //cout << "222" << endl;
                if(cal % 2){
                    b.second -= cal / 2;
                    cnt++;
                }
                else{
                    b.second -= cal / 2;
                }
                res += maxn;
                maxn = b.first;
                int num = b.second / (k / 2);
                cal = k - 2 * (b.second % (k / 2));
                res += num * maxn;
                if(cal == k) maxn = -1;
                
            }
            else{
                //cout << "333" << endl;
                cal = cal - b.second * 2;
            }
        }
        //cout << res << ' ' << cal << endl;
    }
    if(cal != k){
        res += maxn;
    }
    cout << res << endl;
}
signed main() {
    IOS;
    int T = 1;
    cin >> T;
    while (T--){
        solve();
    }
}
inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
    return x * f;
}
inline void write(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar('0' + x % 10);
}