#include<bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define MAXA(x, y) (x) = ((x) > (y)) ? (x) : (y)
#define MINA(x, y) (x) = ((x) < (y)) ? (x) : (y)
#define MAX(x, y) ((x) > (y)) ? (x) : (y)
#define MIN(x, y) ((x) < (y)) ? (x) : (y)
#define ADD(x, y, mod) (x) = (((x)+(y) >= (mod)) ? ((x)+(y) - (mod)) : (((x)+(y) < 0) ? ((x)+(y)+(mod)) : ((x)+(y))) )
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define vi vector<int>
#define count1(x) __builtin_popcount(x)
#define endl '\n'
using namespace std;

// lllllllllllll
const int N = 102;

void test_case(){
    ll n, k;
    cin >> n >> k;
    pair<int, pii> P[n];
    ll answer = 0;
    for(int i = 0; i < n; i++){
        cin >> P[i].ss.ff >> P[i].ss.ss >> P[i].ff;
        if(P[i].ss.ss == 1){
            answer += P[i].ss.ff/k*P[i].ff;
            P[i].ss.ff %= k;
        } else {
            answer += P[i].ss.ff*2/k*P[i].ff;
            P[i].ss.ff = P[i].ss.ff*2%k/2;
        }
    }

    sort(P, P+n);

    vector<int> v;
    for(int i = 0; i < n; i++){
        if(P[i].ss.ss == 1){
            v.push_back(i);
        }
    }


    int p = n-1;
    while(p >= 0){
        ll cur = 0;
        answer += P[p].ff;
        while(p >= 0 && cur <= k-1){
            auto [f, a] = P[p];
            auto [c, w] = a;
            ll rao = min((k - cur)/w, (ll)c);
            cur += rao * w;
            P[p].ss.ff -= rao;
            assert(P[p].ss.ff >= 0);
            if(P[p].ss.ff == 0) p--;
            //cout << cur << endl;
        }


        if(cur < k && p >= 0){
            while(v.size() > 0 && P[v.back()].ss.ff == 0) v.pop_back();
            if(v.size()){
                P[v.back()].ss.ff--;
                if(P[v.back()].ss.ff == 0) v.pop_back();
            }
        }
    }

    cout << answer << endl;
}

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t = 1;
    cin >> t;
    while(t--){
        test_case();
    }
    
}