#include <cstdio>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#define N 100000
using namespace std;
int n,k,T;
vector<pair<int,int>> a[2];
int main()
{
    for(scanf("%d",&T);T--;)
    {
        scanf("%d %d",&n,&k);
        a[0].clear(),a[1].clear();
        for(int i=1,c,w,f;i<=n;++i)
        {
            scanf("%d %d %d",&c,&w,&f);
            a[w&1].push_back({f,c});
        }
        for(int i=0;i<2;++i)
            sort(a[i].begin(),a[i].end(),greater<pair<int,int>>());
        long long ans=0;
        for(int i=0,j=0,c,w,nowk=0;i<a[0].size() || j<a[1].size();)
            if(j==a[1].size() || (i<a[0].size() && a[0][i].first>=a[1][j].first && !(nowk&1)))
            {
                if(a[0][i].second*2<=nowk)
                    nowk-=a[0][i].second*2,a[0][i].second=0;
                else a[0][i].second-=nowk/2,nowk=0;
                ans+=a[0][i].second/(k/2)*a[0][i].first;
                a[0][i].second%=k/2;
                if(a[0][i].second) ans+=a[0][i].first,nowk=k-a[0][i].second*2;
                ++i;
            }
            else
            {
                if(nowk&1)
                {
                    --nowk,--a[1][j].second;
                    if(!a[1][j].second) ++j;
                    continue;
                }
                if(a[1][j].second<=nowk)
                    nowk-=a[1][j].second,a[1][j].second=0;
                else a[1][j].second-=nowk,nowk=0;
                ans+=a[1][j].second/k*a[1][j].first;
                a[1][j].second%=k;
                if(a[1][j].second) ans+=a[1][j].first,nowk=k-a[0][i].second;
                ++j;
            }
        printf("%lld\n",ans);
    }
    return 0;
}