#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        long long k;
        cin >> n >> k;
        map<int, vector<long long>> z;
        for (int i = 0; i < n; i++) {
            int c, w, f;
            cin >> c >> w >> f;
            w--;
            if (!z.count(f)) {
                z[f] = vector<long long>(2, 0);
            }
            z[f][w] += c;
        }
        long long ans = 0;
        vector<pair<int, vector<long long>>> y;
        for (auto p : z) {
            y.emplace_back(p);
        }
        reverse(y.begin(), y.end());
        long long c = 0, d = 0;
        for (auto p : y) {
            long long a = p.second[0];
            long long b = p.second[1];
            long long f = p.first;
            long long mn = min(a, d);
            a -= mn;
            d -= mn;
            long long x = (2 * b + a - c + k - 1) / k;
            ans += x * f;
            c = c + k * x - 2 * b;
            c -= (a + 1) / 2 * 2;
            d += (a + 1) / 2 * 2;
            d -= a;
            // cerr << f << " " << x << " " << a << " " << b << " " << c << " " << d << endl;
        }
        cout << ans << '\n';
    }
}