# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
using i64 = long long;
int n; i64 k; 
pair<int, int> A[N]; // <f, c>
int main(void)
{
	// freopen("in.in", "r", stdin);
	int Test; scanf("%d", &Test); 
	while(Test--)
	{
		scanf("%d%lld", &n, &k); 
		for(int i = 1; i <= n; i++)
		{
			int c, w, f; scanf("%d%d%d", &c, &w, &f); 
			if(w == 2) c <<= 1; 
			A[i] = {f, c}; 
		}
		sort(A + 1, A + n + 1); reverse(A + 1, A + n + 1); 
		i64 ans = 0, sum = 0; int st = 1;
		for(int i = 1; i <= n; i++)
		{
			// printf("i = %d, first = %d, second = %d\n", i, A[i].first, A[i].second);
			if(sum + A[i].second < k) sum += A[i].second; 
			else if(sum + A[i].second == k) sum = 0, ans += A[st].first, st = i + 1; 
			else
			{
				A[i].second -= (k - sum); ans += A[st].first; sum = 0; 
				i64 blo = (A[i].second / k); ans += A[i].first * blo;
				A[i].second %= k; sum += A[i].second;
				if(sum == 0) st = i + 1;
				else st = i; 
			}
			// printf("ans = %lld, sum = %lld\n", ans, sum);
		}
		if(st <= n && sum < k) ans += A[st].first;
		printf("%lld\n", ans);
	}
	return 0; 
}