#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int M=1e5+5;
int T;
int n;
LL k;
struct info {
    int c,w,f;
    bool operator <(const info &_)const {
        return f>_.f;
    }
}p[M];
int stk[M];
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%d%lld",&n,&k);
        for(int i=1; i<=n; ++i)
            scanf("%d%d%d",&p[i].c,&p[i].w,&p[i].f);
        sort(p+1,p+n+1);
        int top=0;
        for(int i=1; i<=n; ++i)
            if((p[i].c&1)&&p[i].w==1)stk[++top]=p[i].f;
        LL now=k/2;
        int L=1,Mx=0;
        LL ans=0;
        for(int i=1; i<=n; ++i) {
            if(now==k/2)Mx=p[i].f;
            if(p[i].w==1)p[i].c/=2;
            if(p[i].c<=now)now-=p[i].c;
            else {
                ans+=Mx;
                p[i].c-=now;
                ans+=1LL*p[i].f*(p[i].c/(k/2));
                p[i].c=p[i].c%(k/2);
                now=k/2-p[i].c;
                if(p[i].c)Mx=p[i].f;
            }
            now=now*2;
            while(L<=top&&stk[L]==p[i].f) {
                if(now==k)Mx=p[i].f;
                now--;
                if(now==0)ans+=Mx,now=k;
                ++L;
            }
            if((now&1)&&L<=top) {
                now--;
                if(now==0)ans+=Mx,now=k;
                ++L;
            }
            if(i==n&&now!=k)ans+=Mx;
            now/=2;
            //cout<<"---"<<now<<" "<<Mx<<" "<<L<<" "<<ans<<" "<<p[i].f<<endl;
        }
        printf("%lld\n",ans);
    }
    return 0;
}