#include<cstring>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#include<string>
#include<queue>
#include<cmath>
#include<iostream>
#include<iomanip>

using namespace std;

#define fi first
#define se second
#define lowbit(x) ((x)&(-x))
#define endl '\n'

const int N=1e5+10,M=3.2e6+10,mod=1e9+7,INF=0x3f3f3f3f;
typedef long long LL;
typedef __int128 LLL;
typedef pair<int,int> PII;
LL t,n,m,k;
LL res;
vector<PII>odd;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>k;
        res=0;
        odd.clear();
        while(n--){
            int c,w,f;
            cin>>c>>w>>f;
            if(w==2)c*=2;
            odd.push_back({f,c});
        }
        sort(odd.begin(),odd.end());
        reverse(odd.begin(),odd.end());
        LL last=0;
        for(auto&[f,c]:odd){
            if(last){
                int val=min(last,1ll*c);
                last-=val;
                c-=val;
            }
            if(c){
                res+=(c+k-1)/k*f;
                last+=(k-c%k)%k;
            }
        }
        cout<<res<<endl;
    }
    return 0;
}