#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int t, n, mno[N];ll k, ans;
struct pkg{int c, w, f;}p[N];

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        ans = 0;
        scanf("%d%lld", &n, &k);
        for(int i = 1;i <= n;i++)scanf("%d%d%d", &p[i].c, &p[i].w, &p[i].f);
        sort(p + 1, p + n + 1, [](pkg a, pkg b){return a.f == b.f ? a.w > b.w : a.f > b.f;});
        for(int i = 1;i <= n;i++)
            if(p[i].f == p[i - 1].f && p[i].w == p[i - 1].w)
                p[i].c += p[i - 1].c, p[i - 1].f = p[i - 1].w = p[i - 1].c = 0;
        sort(p + 1, p + n + 1, [](pkg a, pkg b){return a.f == b.f ? a.w > b.w : a.f > b.f;});
        ll tmp = k;int hig = p[1].f;
        for(int i = 1;i <= n;i++)
        {
            if(!tmp)ans += hig, hig = p[i].f, tmp = k;
            if(1ll * p[i].c * p[i].w <= tmp)tmp -= 1ll * p[i].c * p[i].w, p[i].c = 0;
            else
            {
                if(tmp != k)
                {
                    ans += hig, p[i].c -= tmp / p[i].w, tmp %= p[i].w, hig = p[i].f;
                    if(tmp & 1)
                        for(int j = i + 1;j <= n;j++)
                            if(p[i].c && p[i].w & 1)
                            {
                                p[i].c--;
                                break;
                            }
                    tmp = k;
                }
                ans += 1ll * p[i].c / (k / p[i].w) * p[i].f, p[i].c %= k / p[i].w;
                tmp -= 1ll * p[i].c * p[i].w, p[i].c = 0, hig = p[i].f;
            }
        }
        ans += hig, printf("%lld\n", ans);
    }
    return 0;
}