#include <bits/stdc++.h>

int main()
{
    int _;
    for(scanf("%d",&_);_;_--)
    {
        long long n,k;
        scanf("%lld%lld",&n,&k);
        std::vector<std::array<int,3> > p(n);
        for(int i=0;i<n;i++)
        {
            int c,w,f;
            scanf("%d%d%d",&c,&w,&f);
            p[i]={f,w,c};
        }
        std::sort(p.begin(),p.end());
        long long ans=0,t=k;
        int mf=0;
        for(int i=n-1,j=n;i >= 0;i--)
        {
            int& f=p[i][0],w=p[i][1],c=p[i][2];
            while(c)
            {
                if(c)
                    mf=std::max(f,mf);
                long long x=std::min(t/w,c*1ll);
                c -= x;
                t -= x*w;
                if(t == 0ll)
                {
                    ans += mf;
                    t=k;
                    mf=0;
                    long long tt=c*w/k;
                    ans += tt*f;
                    c -= tt*k/w;
                }
                else
                    if(t == 1ll && c)
                    {
                        j=std::min(i-1,j);
                        while(~j && p[j][1] == 2)
                            j--;
                        if(~j)
                        {
                            p[j][2]--;
                            if(!p[j][2])
                                j--;
                        }
                        ans += mf;
                        t=k;
                        mf=0;
                    }
            }
        }
        if(t != k)
            ans += mf;
        printf("%lld\n",ans);
    }
    return 0;
}