#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ull = unsigned long long;

#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define endl "\n"
#define int long long

void solve() {
    set<int> s1, s2;
    map<int, pair<int, int>> mp;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int c, w, f;
        cin >> c >> w >> f;
        mp[f].first += c * w;
        s2.insert(f);
        if (w == 1) {
            mp[f].second += c;
            s1.insert(f);
        }
    }
    int ans = 0;
    while (!s2.empty()) {
        int t = *(--s2.end());
        s2.erase(t);
        s1.erase(t);
        ans += (mp[t].first + m - 1) / m * t;
        cerr << ans << endl;
        int left = (m - mp[t].first % m) % m;
        while (left && !s2.empty()) {
            if (left % 2 && !s1.empty()) {
                auto t1 = *(--s1.end());
                mp[t1].second--;
                mp[t1].first--;
                if (mp[t1].second == 0) {
                    s1.erase(t1);
                }
                if (mp[t1].first == 0) {
                    s2.erase(t1);
                }
                left--;
            }
            if (!s2.empty()) {
                auto t2 = *(--s2.end());
                if (left >= mp[t2].first) {
                    s2.erase(t2);
                    s1.erase(t2);
                    left -= mp[t2].first;
                } else {
                    mp[t2].first -= left;
                    mp[t2].second = min(mp[t2].first, mp[t2].second);
                    left = 0;
                }
            }
        }
    }
    cout << ans << endl;
}


signed main() {
    IOS
    int t;
    cin >> t;
    while (t--)solve();
}
//2
//4 6
//1 1 8
//7 2 5
//1 1 7
//3 2 6