#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 int 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;

signed 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, cnt, dc, i = 1 ; i <= n ;){
            if(lst == nk && item[i].wi * item[i].ci >= nk){
                cnt = (item[i].wi * item[i].ci) / nk;
                lc = (nk * cnt) / item[i].wi;
                item[i].ci -= lc;
                ans += cnt * lstans;
                if(nk % item[i].wi){
                    while(!site.empty() && cnt){
                        if(item[site.front()].ci){
                            dc = min(item[site.front()].ci, (long long)cnt);
                            item[site.front()].ci -= dc;
                            cnt -= dc;
                        }
                        if(!item[site.front()].ci)
                            site.pop();
                    }
                }
                while(i <= n && item[i].ci == 0){
                    i++;
                    lstans = item[i].fi;
                }
                if(i > n){
                    break;
                }
            }
            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;
}