#include <bits/stdc++.h>
using namespace std;

#define qmx(a,b) a<b?b:a
#define qmn(a,b) a>b?b:a
#define ll long long
#define fr first
#define se second

const int mxn = 1e5+5;

struct Item{
    ll ci;
    int wi;
    int fi;
}item[mxn];

int n;

ll nk, ans, lst, lstans;

inline bool cmp(struct Item i1, struct Item i2){
    return i1.fi > i2.fi;
}

queue <int> site;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test;
    cin>>test;
    while(test--){
        ans = 0;
        cin >> n >> nk;
        for(int i = 1 ; i <= n ; i++){
            cin >> item[i].ci >> item[i].wi >> item[i].fi;
        }
        sort(item + 1, item + 1 + n, cmp);
        while(!site.empty())
            site.pop();
        for(int i = 1 ; i <= n ; i++){
            if(item[i].wi == 1)
                site.push(i);
        }
        lst = nk;
        lstans = item[1].fi;
        for(int lc, i = 1 ; i <= n ;){
            lc = min(lst / item[i].wi, item[i].ci);
            item[i].ci -= lc;
            lst -= lc * item[i].wi;
            if(lst == 1){
                while(!site.empty() && item[site.front()].ci == 0)
                    site.pop();
                if(!site.empty()){
                    lst--;
                    item[site.front()].ci--;
                }
            }
            while(i <= n && item[i].ci == 0)
                i++;
            if(i > n){
                ans += lstans;
                break;
            }
            if(!lst || lst == 1 && site.empty()){
                lst = nk;
                ans += lstans;
                lstans = item[i].fi;
            }
        }
        cout << ans << endl;
    }
    return 0;
}