#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 5 ;
using ll = long long ;

int n ;
int c[N], w[N] ;
ll k ;

void solve()
{
    cin >> n >> k ;
    map<int, pair<ll, ll>, greater<int>> goods ;
    for(int i = 1; i <= n; ++ i)
    {
        int x ; cin >> c[i] >> w[i] >> x ;
        if(w[i] == 1) goods[x].first += c[i] ;
        else goods[x].second += c[i] ;
    }

    vector<int> a ;
    for(auto [dep, pir] : goods)
        if(pir.first) a.push_back(dep) ;

    reverse(a.begin(), a.end()) ;

    // for(auto x : a) cout << x << ' ' ;
    // cout << '\n' ;

    ll ans = 0, sur = 0, nowdep = 0 ;

    // for(auto [dep, pir] : goods) cout << dep << ' ' << pir.first << ' ' << pir.second << '\n' ;

    for(auto [dep, pir] : goods)
    {
        auto [x, y] = pir ;
        if(x == 0 && y == 0) continue ;

        // cout << "! " << dep << ' ' << sur << ' ' << x << ' ' << y << '\n' ;

        while(!a.empty() && (a.back() >= dep || goods[a.back()].first == 0)) a.pop_back() ;

        if(nowdep == 0) nowdep = dep ;

        if(y * 2 + sur > k)
        {
            ll z = (k - sur) / 2 ;
            // ans += nowdep ;
            y -= z ; sur += z * 2 ;

            if(sur < k)
            {
                if(x) x --, sur ++ ;
                else if(!a.empty())
                {
                    // cout << "JJJJJJJJJJJJJJJJJ" << ' ' << a.back() << '\n' ;
                    goods[a.back()].first -- ;
                    sur ++ ;
                }
            }

            ans += nowdep ;

            // cout << sur << ' ' << dep << ' ' << nowdep << '\n' ;

            sur = 0 ; nowdep = 0 ;
            // cout << "? " << dep << ' ' << x << ' ' << y << '\n' ;

            ll q = y * 2 / k ;
            ans += q * dep ;
            y -= q * (k / 2) ;
            // cout << "K " << dep << ' ' << ans << ' ' << x << ' ' << y << '\n' ;
            if(y) sur = y * 2, nowdep = dep ;
        }
        else
        {
            sur += y * 2 ;
            if(sur == k)
            {
                ans += nowdep ;
                // cout << sur << ' ' << dep << ' ' << nowdep << '\n' ;
                sur = 0, nowdep = 0 ;
            }
        }

        if(x && nowdep == 0) nowdep = dep ;

        if(sur + x > k)
        {
            x -= k - sur ;
            ans += nowdep ;
            sur += k - sur ;
            // cout << sur << ' ' << dep << ' ' << nowdep << '\n' ;

            sur = nowdep = 0 ;

            ll z = x / k ;
            ans += dep * z ;
            x -= z * k ;

            if(x) sur = x, nowdep = dep ;
        }
        else
        {
            sur += x ;
            if(sur == k) ans += nowdep, sur = nowdep = 0 ;
        }
        // cout << "ANS " << dep << ' ' << ans << '\n' ;
    }

    // cout << sur << ' ' << nowdep << '\n' ;

    if(sur) ans += nowdep ;
    cout << ans << '\n' ;
}

int main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;

    int T ; cin >> T ;
    while(T --) solve() ;
    return 0 ;
}