///////////        
//                   //      //
//              ////////////////////
//                   //      //
//                 
///////////

//          
//          
//           //     //    ////////     /\     /////////
//           //     //   //      //          //       //
//            ////////   //      //    //    //       //
//                  //   //      //    //    //       //
//////////   ////////    //      //    //     /////////////

#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <stack>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <random>
#include <numeric>
#include <functional>
//#include <Windows.h>

using namespace std;

#define fa(i,op,n) for (int i = op; i <= n; i++)
#define fb(j,op,n) for (int j = op; j >= n; j--)
#define pb push_back
#define HashMap unordered_map
#define HashSet unordered_set
#define var auto
#define all(i) i.begin(), i.end()
#define all1(i) i.begin() + 1,i.end()
#define endl '\n'
#define px first
#define py second
#define DEBUG(a) cout<<a<<endl

using VI = vector<int>;
using VL = vector<long long>;
using ll = long long;
using ull = unsigned long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
	out << '(' << p.first << ", " << p.second << ')';
	return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& ve) {
	for (T i : ve)
		out << i << ' ';
	return out;
}

template<class T1, class T2>
ostream& operator<<(ostream& out, const map<T1, T2>& mp) {
	for (auto i : mp)
		out << i << '\n';
	return out;
}

const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int IINF = 0x7fffffff;
const int iinf = 0x80000000;
const ll LINF = 0x7FFFFFFFFFFFFFFF;
const ll linf = 0x8000000000000000;
int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };

//#include "Lynia.h"

const int mod = 998244353;
const int N = 1e6 + 10;

struct node {
	ll c, w, f;
	bool operator<(const node& a)const {
		if (f == a.f)return w > a.w;
		if (f == a.f and c == a.c)return c > a.c;
		return f > a.f;
	}
};
void solve(int CASE)
{
	ll n, k; cin >> n >> k;
	multiset<node>Q, se_w_1;
	fa(i, 1, n) {
		ll c, w, f; cin >> c >> w >> f;
		Q.insert({ c,w,f });
	}
	ll ans = 0;

	ll last = 0;       // 上一个包裹还剩的可装重量
	ll last_f = 0;     // 上一个包裹装的最大目标位置
	while (Q.size()) { // 得保证每次都把当前用完
		var[c, w, f] = *Q.begin();
		//cout << c << ' ' << w << ' ' << f << endl;
		Q.erase(Q.begin());
		if (w == 1) {
			var it = se_w_1.find({ c,w,f });
			if (it != se_w_1.end())se_w_1.erase(it);
		}

		// [-] 处理剩 1 装满的包裹
		var f1 = [&](ll num)->void {
			while (se_w_1.size() and num) {
				var origin = *se_w_1.begin();

				var now = se_w_1.begin()->c;
				se_w_1.erase(se_w_1.begin());

				var it = Q.find(origin);
				Q.erase(it);

				ll tmp = min(c, num);
				c -= tmp;
				num -= tmp;

				if (c != 0) {
					origin.c = c;
					se_w_1.insert(origin);
					Q.insert(origin);
				}
			}
			};


		// 1. 弥补上一个包裹的
		var tmp = (k - last) / w;
		if (c >= tmp) { // 能弥补
			c -= tmp;

			last += tmp * w;
			last_f = max(last_f, f);

			ans += last_f;
			if (k - last == 1)f1(1);

			last = 0;
			last_f = 0;
		}


		// 2. 还有剩的就接着开若干个装满的新包装
		var num = k / w;      // 每个新包装多少物品
		var per_w = num * w;  // 每个新包装多重
		var mx_cnt = c / num; // 最多装几个完整新包

		c -= mx_cnt;
		ans += mx_cnt * f;

		if (k - per_w == 1)f1(mx_cnt);


		// 3. 产生新的 last 或继承上一个 last
		if (c != 0) {
			last += c * w;
			last_f = max(last_f, f);
		}
		//cout << f << ' ' << ans << endl;
	}
	if (last)ans += last_f;

	cout << ans << endl;
	return;
}

int main()
{
	//SetConsoleOutputCP(CP_UTF8);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	fa(i, 1, _)solve(i);
	return 0;
}