#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define gcd __gcd
using namespace std;
typedef pair<int,int> pii;
const int INF = 9e18;
const int inf = 2e9;

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t --)
    {
        int n,k;
        cin >> n >> k;
        vector<array<int,3>> a(n + 1);
        vector<int> res;
        for(int i = 1;i <= n;i ++)
        {
            int c,w,f;
            cin >> c >> w >> f;
            a[i] = {f,c,w};
            // if(w & 1) res.push_back(i);
        }
        sort(a.begin()+1,a.end());
        for(int i = 1;i <= n;i ++)
        {
            if(a[i][2] & 1) res.push_back(i);
        }

        int ans = 0,sum = 0;
        for(int i = n,j = n;i >= 1;i --)
        {
            while(j >= 1 && a[j][1] <= 0) j --;

            if(sum + a[i][1] * a[i][2] <= k)
            {
                sum += a[i][1] * a[i][2];
                if(sum == k || i == 1)
                {
                    ans += a[j][0];
                    j = i - 1;
                    sum = 0;
                }
            }
            else
            {
                int tep = (k - sum) / a[i][2] * a[i][2];
                sum += tep;
                int lst = a[i][1] * a[i][2] - tep;
                if(sum < k)
                {
                    while(res.size() && a[res.back()][0] >= a[i][0]) res.pop_back();
                    int y = 1;
                    if(res.size() && y)
                    {
                        int x = res.back();
                        if(y >= a[x][1])
                        {
                            y -= a[x][1];
                            a[x][1] = 0;
                            res.pop_back();
                        }
                        else a[x][1] -= y;
                    }
                }
                sum = 0;
                ans += a[j][0];
                if(lst >= k)
                {
                    int cn = lst / a[i][2];
                    int cnt = lst / k;
                    ans += a[i][0] * cnt;
                    int l = 0,r = cn;
                    while(l < r)
                    {
                        int mid = l + r + 1 >> 1;
                        if(mid * a[i][2]) l = mid;
                        else r = mid - 1;
                    }
                    int x = l * a[i][2];
                    while(res.size() && a[res.back()][0] >= a[i][0]) res.pop_back();
                    while(x < k && cnt && res.size())
                    {
                        int y = res.back();
                        if(cnt >= a[y][1])
                        {
                            res.pop_back();
                            cnt -= a[y][1];
                            a[y][1] = 0;
                        }
                        else a[y][1] -= cnt;
                    }
                    lst %= k;
                }

                sum = lst;
                if(sum > 0) j = i;
                else j = i - 1;
                if(i == 1 && sum) ans += a[i][0];
            }
        }
        cout << ans << endl;
    }
}