#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <unordered_map>
#include <iomanip>
#define endl '\n'
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rep2(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
template<typename T>
void cc(const vector<T>& tem) { for (const auto& x : tem) cout << x << ' '; cout << endl; }
template<typename T>
void cc(const T& a) { cout << a << endl; }
template<typename T1, typename T2>
void cc(const T1& a, const T2& b) { cout << a << ' ' << b << endl; }
template<typename T1, typename T2, typename T3>
void cc(const T1& a, const T2& b, const T3& c) { cout << a << ' ' << b << ' ' << c << endl; }
void cc(const string& s) { cout << s << endl; }
void fileRead() {
#ifdef LOCALL
    freopen("D:\\AADVISE\\cppvscode\\CODE\\in.txt", "r", stdin);
    freopen("D:\\AADVISE\\cppvscode\\CODE\\out.txt", "w", stdout);
#endif
}
void kuaidu() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); }
inline int max(int a, int b) { if (a < b) return b; return a; }
inline double max(double a, double b) { if (a < b) return b; return a; }
inline int min(int a, int b) { if (a < b) return a; return b; }
inline double min(double a, double b) { if (a < b) return a; return b; }
void cmax(int& a, const int& b) { if (b > a) a = b; }
void cmin(int& a, const int& b) { if (b < a) a = b; }
void cmin(double& a, const double& b) { if (b < a) a = b; }
void cmax(double& a, const double& b) { if (b > a) a = b; }
using PII = pair<int, int>;
using i128 = __int128;
using vec_int = std::vector<int>;
using vec_char = std::vector<char>;
using vec_double = std::vector<double>;
using vec_int2 = std::vector<std::vector<int>>;
using que_int = std::queue<int>;


//--------------------------------------------------------------------------------
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e16;
int n, m, T;

//--------------------------------------------------------------------------------
//struct or namespace:
struct node {
    int c;
    int to;
};
//--------------------------------------------------------------------------------

int dfs(vector<node>& A) {
    sort(A.begin(), A.end(), [&](const node& q1, const node& q2) {
        return q1.to > q2.to;
        });
    int len = A.size();
    int ans = 0;
    rep(i, 0, len - 1) {
        if (A[i].c <= 0 and i < len - 1) {
            A[i + 1].c += A[i].c;
            continue;
        }
        if (i == len - 1) {
            ans += (A[i].c + m - 1) / m * A[i].to;
            continue;
        }
        ans += (A[i].c + m - 1) / m * A[i].to;
        if (A[i].c % m) A[i + 1].c -= m - (A[i].c % m);
    }
    return ans;

}

signed main() {
    fileRead();
    kuaidu();
    T = 1;
    cin >> T;
    while (T--) {
        cin >> n >> m; m /= 2;
        vector<node> F, A;
        rep(i, 1, n) {
            int c, w, f; cin >> c >> w >> f;
            if (w == 2) {
                A.push_back({ c,f });
                continue;
            }
            F.push_back({ c,f });
        }
        sort(F.begin(), F.end(), [&](const node& q1, const node& q2) {
            return q1.to > q2.to;
            });
        int len = F.size();
        rep(i, 0, len - 1) {
            if (i == len - 1) {
                A.push_back({ (F[i].c + 1) / 2,F[i].to });
                continue;
            }
            A.push_back({ (F[i].c + 1) / 2,F[i].to });
            if (F[i].c % 2) F[i + 1].c -= 1;
        }

        cc(dfs(A));
        // cc(ans);
    }
    return 0;
}
/*


*/