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

#define int i64
void solve() {
    int n, k;
    cin >> n >> k;
    multiset<tuple<int, int, int>> st;
    multiset<pair<int, int>> stw[3];
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int c, w, f;
        cin >> c >> w >> f;
        st.insert({f, w, c});
        stw[w].insert({f, c});
    }
    int rem_size = 0;
    while (st.size()) {
        if (rem_size) {
            if (rem_size > 1) {
                auto it = --st.end();
                auto [f, w, c] = *it;
                st.erase(it);
                stw[w].extract({f, c});
                int use_count = min(rem_size / w, c);
                c -= use_count;
                rem_size -= use_count * w;
                if (c) {
                    st.insert({f, w, c});
                    stw[w].insert({f, c});
                }
            } else {
                if (stw[1].size()) {
                    int w = 1;
                    auto it = --stw[w].end();
                    auto [f, c] = *it;
                    st.extract({f, w, c});
                    stw[w].erase(it);
                    int use_count = 1;
                    c -= use_count;
                    rem_size -= use_count;
                    assert(rem_size == 0);
                    if (c) {
                        st.insert({f, w, c});
                        stw[w].insert({f, c});
                    }
                } else {
                    rem_size--;
                }
            }
        } else {
            auto it = --st.end();
            auto [f, w, c] = *it;
            st.erase(it);
            stw[w].extract({f, c});
            {
                int divide = (c * w) / k;
                if (divide) {
                    c -= (divide * k) / w;
                    ans += divide * f;
                }
            }
            if (c) {
                rem_size += k;
                ans += f;
                st.insert({f, w, c});
                stw[w].insert({f, c});
            }
        }
    }
    cout << ans << "\n";
}
#undef int

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}