#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+1;
int f[N];
signed main()
{
	int t;
	cin>>t;
	int n,k,maxh=0;
	while(t--)
	{
		
		memset(f,0,maxh);
		maxh=0;
		cin>>n>>k;
		for (int i=1;i<=n;i++)
		{
			int s,v,h;
			cin>>s>>v>>h;
			f[h]+=s*v;
			maxh=max(maxh,h);
		}
		int res=0,ans=0;
		for (int i=maxh;i>=1;i--)
		{
			if (f[i])
			{
				if (f[i]>res)
				{
					f[i]-=res;
					ans+=(f[i]+k-1)/k*i;
					res=k-(f[i]%k);
				}
				else res-=f[i];
			}
		}
		cout<<ans<<endl;
	}
 }