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

void solve() {
    int n;
    LL k;
    cin >> n >> k;

    array<vector <array<int, 2>>, 2> a{};
    for (int i = 0; i < n; ++i) {
        int c, w, f;
        cin >> c >> w >> f;
        a[w - 1].push_back({f, c});
    }
    sort(a[0].begin(), a[0].end());
    sort(a[1].begin(), a[1].end());

    int id0 = (int)a[0].size() - 1;
    int id1 = (int)a[1].size() - 1;

    LL ans = 0;
    LL rem = k;

    auto norm = [&]() {
        while (id0 >= 0 && a[0][id0][1] == 0) {
            --id0;
        }
    };

    auto op0 = [&]() {
        LL t1 = rem;
        if (rem == k) {
            ans += a[0][id0][0];
        }

        if (t1 > a[0][id0][1]) {
            rem -= a[0][id0][1];
            a[0][id0][1] = 0;
        } else {
            rem -= t1;
            a[0][id0][1] -= t1;
        }

        if (rem == 0) {
            rem = k;
        }

        if (a[0][id0][1] > 0) {
            LL cnt = a[0][id0][1] / k;
            LL t = a[0][id0][1] % k;

            ans += cnt * a[0][id0][0];
            if (t) {
                ans += a[0][id0][0];
                rem = k - t;
            } else {
                rem = k;
            }
        }

        id0--;

        if (rem == 1) {
            if (id0 >= 0) {
                a[0][id0][1]--;
            }
            norm();    
            rem = k;
        } else if (rem == 0) {
            rem = k;
        }
    };

    auto op1 = [&]() {
        LL t1 = rem / 2;
        if (rem == k) {
            ans += a[1][id1][0];
        }

        if (t1 > a[1][id1][1]) {
            rem -= a[1][id1][1] * 2;
            a[1][id1][1] = 0;
        } else {
            rem -= t1 * 2;
            a[1][id1][1] -= t1;
        }

        if (rem == 1) {
            if (id0 >= 0) {
                a[0][id0][1]--;
            }
            norm();    
            rem = k;
        } else if (rem == 0) {
            rem = k;
        }

        if (a[1][id1][1] > 0) {
            LL cnt = a[1][id1][1] / (k / 2);
            LL t = a[1][id1][1] % (k / 2);

            ans += cnt * a[1][id1][0];
            if (t) {
                ans += a[1][id1][0];
                rem = k - t * 2;
            } else {
                rem = k;
            }
        }
        id1--;

        if (rem == 1) {
            if (id0 >= 0) {
                a[0][id0][1]--;
            }
            norm();    
            rem = k;
        } else if (rem == 0) {
            rem = k;
        }
    };

    while (id0 >= 0 || id1 >= 0) {
        if (id0 >= 0 && id1 >= 0) {
            if (a[0][id0][0] <= a[1][id1][0]) {
                op1();
            } else {
                op0();
            }
        } else if (id0 >= 0) {
            op0();
        } else {
            op1();
        }
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}