#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;
    // int tt = t;
    // int u = 0;
    while(t --)
    {
        // u ++;
        int n,k;
        cin >> n >> k;
        vector<array<int,3>> a;
        for(int i = 1;i <= n;i ++)
        {
            int f,c,w;
            cin >> c >> w >> f;
            // a[i] = {f,c,w};
            if(c > 0)
            {
                a.push_back({f,c,w});
            }
        }
        sort(a.begin(),a.end());
        int ans = 0;
        vector<int> res;
        n = a.size() - 1;
        for(int i = 0;i < a.size();i ++)
        {
            if((a[i][2] & 1))
            {
                res.push_back(i);
            }
        }

        int sum = 0,lst = 0;
        for(int i = n,j = n;i >= 0;i --)
        {
            while(j >= 0 && a[j][1] <= 0) j --;
            // if(j < 0) break;
            if(sum + a[i][1] * a[i][2] <= k)
            {
                sum += a[i][1] * a[i][2];
                if(sum == k || i == 0)
                {
                    ans += a[j][0];
                    j = i - 1;
                    sum = 0;
                }
                continue;
            }

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

        cout << ans << endl;
    }
}