#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define Enter putchar('\n')
#define spc putchar(' ')
#define pb push_back
#define fi first
#define se second
inline void read(int &num){num=0;int f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch^48);ch=getchar();}num*=f;}
inline void lread(long long &num){num=0;int f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){num=(num<<1)+(num<<3)+(ch^48);ch=getchar();}num*=f;}
void print(long long num){if(num<0){putchar('-');num=-num;}if(num>9){print(num/10);}putchar((num%10)^48);}
LL f[100009][2];
vector<int> g;
int main(){
    int T,n,a,b,c;
    LL k;
    read(T);
    while(T--){
        read(n),lread(k);
        g.clear();
        for(int i=1;i<=n;i++){
            read(a),read(b),read(c);
            f[c][b-1]+=a;
            g.pb(c);
        }
        sort(g.begin(),g.end());
        LL ans=0,re=0;
        for(int i=g.size()-1;~i;i--){
            f[g[i]][1]<<=1;
            if(f[g[i]][1]>=re){
                if(re&1){
                    f[g[i]][1]-=re-1;
                    re=1;
                }
                else{
                    f[g[i]][1]-=re;
                    re=0;
                }
            }
            else{
                re-=f[g[i]][1];
                f[g[i]][1]=0;
            }
            if(f[g[i]][0]>=re){
                f[g[i]][0]-=re;
                re=0;
            }
            else{
                re-=f[g[i]][0];
                f[g[i]][0]=0;
            }
            ans+=f[g[i]][1]/k*g[i];
            f[g[i]][1]%=k;
            ans+=f[g[i]][0]/k*g[i];
            f[g[i]][0]%=k;
            if(re&&f[g[i]][1]){
                re+=k-f[g[i]][1];
                ans+=g[i];
                f[g[i]][1]=0;
                continue;
            }
            if(re)continue;
            re=f[g[i]][1]+f[g[i]][0];
            f[g[i]][1]=f[g[i]][0]=0;   
            if(re>=k){
                re-=k;
                ans+=g[i];
            }
            if(re){
                re=k-re;
                ans+=g[i];
            }
            //cout<<g[i]<<' '<<ans<<' '<<re<<endl;
        }
        print(ans),Enter;
    }
    return 0;
}