#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{
    int h,num;
}a[100010],b[100010];
int cmp(node x,node y)
{
    return x.h<y.h;
}
int t1,t2,ans;
void solve()
{
    int n,k;
    cin>>n>>k;
    t1=t2=ans=0;
    for(int i=1,x,y,z;i<=n;i++)
    {
        cin>>x>>y>>z;
        if(y==1)a[++t1].num=x,a[t1].h=z;
        else b[++t2].num=x,b[t2].h=z;
    }
    //cout<<t1<<" "<<t2<<endl;
    sort(a+1,a+t1+1,cmp);
    sort(b+1,b+t2+1,cmp);
    while(t1||t2)
    {
        if(b[t2].h>=a[t1].h)
            ans+=b[t2].h;
        else ans+=a[t1].h;
        int kk=k;
        while(t1||t2)
        {
			if(b[t2].h>=a[t1].h)
            {
                if(kk>=b[t2].num*2)
                    kk-=b[t2].num*2,t2--;
                else
                {
                    b[t2].num-=kk/2,kk-=(kk/2)*2;
                    if(kk)
                    {
                        if(a[t1].num==1)t1--;
                        else a[t1].num--;
                    }
					break;
                }
            }
            else
            {
                if(kk>=a[t1].num)
                    kk-=a[t1].num,t1--;
                else
                {
                    a[t1].num-=kk;
                    break;
                }
            }
        }
        //cout<<ans<<endl;
    }
    cout<<ans<<"\n";
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}