#include <bits/stdc++.h>

#define int int64_t

const int kMaxN = 1e5 + 5;

void dickdreamer() {
  int n, k;
  std::cin >> n >> k;
  std::vector<std::tuple<int, int, int>> vec;
  for (int i = 1; i <= n; ++i) {
    int c, w, f;
    std::cin >> c >> w >> f;
    vec.emplace_back(f, 3 - w, c);
  }
  std::sort(vec.begin(), vec.end(), std::greater<>());
  int ans = 0, cnt[3] = {0};
  for (auto [f, w, c] : vec) {
    w = 3 - w;
    // std::cerr << f << ' ' << w << ' ' << c << ' ' << ans << ' ' << cnt[1] << ' ' << cnt[2] << '\n';
    if (cnt[w] >= c) {
      cnt[w] -= c, c = 0;
      continue;
    }
    c -= cnt[w], cnt[w] = 0;
    if (w == 1 && 2 * cnt[2] >= c) {
      int t = c / 2;
      cnt[2] -= t, c -= 2 * t;
      if (c) --cnt[2], ++cnt[1], --c;
    }
    if (!c) continue;
    int bb = k / w, ct = c / bb;
    ans += f * ct, c -= bb * ct;
    if (!c) continue;
    ans += f;
    // std::cerr << "!!! " << c << ' ' << cnt[1] << ' ' << cnt[2] << '\n';
    if (w == 1) {
      cnt[1] += (c & 1);
      cnt[2] += k / 2 - (c + 1) / 2;
    } else {
      cnt[2] += k / 2 - c;
    }
  }
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}