#include<bits/stdc++.h>

#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...) 42
#endif

using i64 = long long;

namespace ranges = std::ranges;

struct Good {
    int c, w, f;
    bool operator < (const Good& rhs) {return f > rhs.f;}
    friend std::ostream& operator << (std::ostream& os, Good& gd) {os << gd.c << " " << gd.w << " " << gd.f << "\n"; return os;}
};

void solve()
{
#define tests
    int n; i64 k; std::cin >> n >> k; std::vector<Good> goods(n); for (auto&[c, w, f] : goods) {std::cin >> c >> w >> f; if (w == 2) {c *= 2;}}

    std::sort(goods.begin(), goods.end()); i64 idx{}, res{}, rem{}; bool is_first{true}; for (auto&[c, _, f] : goods) {    
        i64 now{c + rem};
        if (now > k) {
            res += (now / k) * f;
        } else if (is_first) {
            res += f; now -= 1; is_first = false;
        }
        rem = now % k;
    }

    std::cout << res << "\n";

}

signed main()
{
   std::cin.tie(nullptr)->sync_with_stdio(false);
   int _(1);
#ifdef tests
   std::cin >> _;
#endif
   while(_--) solve();
   return 0;
}