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

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define orange(a...) orange_(#a, a)
#define debug(a...) debug_(#a, a)
#include <experimental/iterator>
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

void solve() {
  int n;
  int64_t k;
  cin >> n >> k;

  vector<tuple<int,int,int>> v(n);

  for (auto &[f, w, c] : v) {
    cin >> c >> w >> f;
  }

  ranges::sort(v, greater<>());

  int64_t total_weight_one = 0;
  for (auto [f, w, c] : v) {
    if (w == 1) {
      total_weight_one += c;
    }
  }

  int64_t current = 0;
  int64_t fnow = -1;
  int64_t ans = 0;
  int borrow = 0;

  for (auto [f, w, c] : v) {

    if (current == 0) {
      fnow = f;
    }

    if (w == 1) {
      int r = min(borrow, c);
      c -= r;
      borrow -= r;
      total_weight_one -= c;
      // debug(c, r);
      // debug(borrow, total_weight_one);
    }

    int64_t z = min((k - current) / w, int64_t(c));
    debug(f, w, c, z);
    current += w * z;
    if (current == k - 1) {
      ans += fnow;
      current = 0;
      // take a weight one
      if (total_weight_one >= 1) {
        borrow += 1;
        total_weight_one -= 1;
        debug("BORROW", borrow, total_weight_one);
      }

      debug(k, w);
      ans += f * ( (c - z) / (k / w) );
      fnow = f;
      current = (c - z) % (k / w) * w;
    } else if (current == k) {
      ans += fnow;
      debug("exact", fnow);
      current = 0;

      ans += f * ( (c - z) / (k / w) );
      current = (c - z) % (k / w) * w;
      fnow = f;
    } else {
      debug(z, c);
    }
  }

  if (current) {
    ans += fnow;
  }

  cout << ans << '\n';
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}