#include <bits/stdc++.h>

using Cargo = std :: pair<int, int>;

std :: vector<Cargo> w1, w2;

int n;
long long k;

void init() {
    w1.clear(), w2.clear();
}

std :: vector<Cargo> combine( std :: vector<Cargo> &cgo, const long long &siz ) {
    std :: sort( cgo.begin(), cgo.end(), std :: greater<Cargo> () );

    long long curSiz = 0;
    int l = cgo.size(), curWei = 0;
    std :: vector<Cargo> ret;

    auto add_new = [&] ( const int &f, const int &c ) -> void {
        if( c == 0 ) return ;
        if( ret.size() && ret.back().first == f )
            ret.back().second ++;
        else ret.emplace_back( f, c );
    };

    for( int i = 0 ; i < l ; i ++ ) {
        int f = cgo[i].first, c = cgo[i].second;
        if( curSiz > 0 ) {
            if( curSiz + c < siz ) {
                curSiz += c; continue;
            }
            add_new( curWei, 1 );
            c -= siz - curSiz;
            curSiz = curWei = 0;
        }
        add_new( f, c / siz );
        if( c % siz )
            curSiz = c % siz, curWei = f;
    }
    if( curSiz ) add_new( curWei, 1 );
    return ret;
}

void solve() {
    long long totWei = 0;
    std :: cin >> n >> k, init();
    for( int i = 1 ; i <= n ; i ++ ) {
        int c, w, f;
        std :: cin >> c >> w >> f;
        ( w == 1 ? w1 : w2 ).emplace_back( f, c );
        totWei += w * c;
    }
    std :: vector<Cargo> &&tmp = combine( w1, 2 );
    for( const auto &c : tmp ) w2.push_back( c );
    std :: vector<Cargo> &&res = combine( w2, k >> 1 );
    long long ans = 0;
    for( const auto &c : res )
        ans += 1ll * c.first * c.second;
    std :: cout << ans << std :: endl;
}

int main() {
    std :: ios :: sync_with_stdio( false );
    int t; std :: cin >> t;
    while( t -- ) solve(); 
    return 0;
}