#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct wp{
    ll h,sum,w;
    bool operator <(const wp s)const{
        return h<s.h;
    }
};
priority_queue<wp>j,o;
ll n,m,t;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m;
        while(j.size())j.pop();while(o.size())o.pop();
        for(int i=1;i<=n;i++){
            int x,y,z;cin>>x>>y>>z;
            if(z&1)j.push({z,x,y});else o.push({z,x,y});
        }
        ll ans=0,lm=0;
        while(j.size() || o.size()){
            if(lm==1){
                lm=0;
                if(!j.empty()){
                    auto u=j.top();j.pop();
                    u.sum--;
                    if(u.sum)j.push(u);
                }
            }
            if(!lm){
                lm=m;
                if(j.empty())ans+=o.top().h;
                else if(o.empty())ans+=j.top().h;
                else ans+=max(j.top().h,o.top().h);
            }
            int cs=0;
            if(j.empty() || (!j.empty() && !o.empty() &&j.top().h<o.top().h))cs=1;
            if(cs==0){
                auto u=j.top();j.pop();
                ll dc=m/u.w;
                if(dc<u.sum){
                    ans+=u.h*(u.sum/dc);
                    u.sum=u.sum%dc;
                }
                if(u.sum>lm/u.w){
                    u.sum-=lm/u.w;
                    lm=lm%u.w;
                    j.push(u);
                }
                else {
                    lm-=u.sum*u.w;
                }
            }
            else {
                auto u=o.top();o.pop();
                ll dc=m/u.w;
                if(dc<u.sum){
                    ans+=u.h*(u.sum/dc);
                    u.sum=u.sum%dc;
                }
                if(u.sum>lm/u.w){
                    u.sum-=lm/u.w;
                    lm=lm%u.w;
                    o.push(u);
                }
                else {
                    lm-=u.sum*u.w;
                }                
            }
        }
        cout<<ans<<'\n';
    }
}