/*
 * 贪心地优先运送去往高层的包裹
 * */
#include <bits/stdc++.h>

using i64 = long long;

const int MAXN = 1e5 + 5;

struct Parcels {
    int c, w, h;
    void init() {
        std::cin >> c >> w >> h;
    }
    bool operator<(const Parcels& p) const {
        return h > p.h;
    }
};

void solve() {
    i64 n, k;
    std::cin >> n >> k;
    std::vector<Parcels> buc(n);
    for(int i = 0; i < n; i++) buc[i].init();
    sort(buc.begin(), buc.end());
    i64 cnt = 0; // 记录应该取走的 w = 1 的包裹的数量
    i64 ans = 0, rem = 0; // rem 表示可用的负载量
    for(auto [c, w, h] : buc) {
        if(w == 1) {
            {
                int t = std::min(cnt, 1LL * c);
                c -= t, cnt -= t;
            }
            if(rem >= c) {
                rem -= c;
            } else {
                c -= rem;
                i64 need = (c + k - 1) / k;
                ans += need * h;
                rem = need * k - c;
            }
        } else {
            if(rem >= c * 2) {
                rem -= c * 2;
            } else {
                c -= rem / 2;
                if(rem % 2) cnt++;
                i64 need = (c + k / 2 - 1) / (k / 2);
                ans += need * h;
                rem = need * k - c * 2;
            }
        }
    }
    std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    std::cin >> T;
    while(T--) solve();

    return 0;
}