#include<bits/stdc++.h>
#define N 100005
#define LL long long
using namespace std;
#define Ms(a,b) memset(a,b,sizeof a)
#define db(x) cerr<<#x<<"="<<x<<endl;
#define db2(x,y) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl;
#define db3(x,y,z) cerr<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl;
LL rd(){
    LL res=0,c,f=0;
    while(!isdigit(c=getchar()))f=c=='-';
    do res=(res<<1)+(res<<3)+(c^48);
    while(isdigit(c=getchar()));
    return f?-res:res;
}
int T,n;
LL k;
struct node{
    int c,w,f;
}a[N];
struct cmp{
    bool operator ()(const node &a,const node &b){
        return a.f==b.f?a.w>b.w:a.f>b.f;
    }
};
int main(){
    T=rd();
    while(T--){
        n=rd(),k=rd();
        for(int i=1;i<=n;i++){
            a[i].c=rd();
            a[i].w=rd();
            a[i].f=rd();
        }
        sort(a+1,a+1+n,cmp());
        queue<int>q;
        for(int i=1;i<=n;i++)if(a[i].w==1&&(a[i].c&1))q.push(i);
        //for(int i=1;i<=n;i++)db3(a[i].c,a[i].w,a[i].f);
        LL res=0;
        int cur=2;
        for(int i=1;i<=n;i++){
            res+=1ll*a[i].c*a[i].w/k*a[i].f;
            a[i].c%=k/a[i].w;
            if((a[i].c&1)&&a[i].w==1){
                if(!q.empty()&&q.front()==i)q.pop();
                if(!q.empty()){
                    int x=q.front();q.pop();
                    a[x].c--;
                }
                a[i].c++;
            }
            if(a[i].c){
                LL now = 1ll*a[i].c*a[i].w;
                cur=max(cur,i+1);
                while(cur<=n&&now<k){
                    while(cur<=n&&a[cur].c==0)++cur;
                    if(cur<=n){
                        LL add = min(k-now, 1ll*a[cur].c*a[cur].w);
                        now+=add;
                        a[cur].c-=add/a[cur].w;
                        if(now&1&&!q.empty()){
                            int x=q.front();q.pop();
                            a[x].c--;
                            now++;
                        }
                    }
                }
                res+=a[i].f;
            }
            //db2(i,res);
            //for(int j=1;j<=n;j++)
                //db3(a[j].c,a[j].w,a[j].f);
        }
        printf("%lld\n",res);
    }
    return 0;
}