#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<climits>
#include<list>
#include<iomanip>
using namespace std;
long long dp[50010][4][2],ans;
int c,w[50010],trap[50010];
vector<int>edge[50010];
void dfs(int pre,int from)
{
	dp[from][trap[from]][trap[from]]=w[from];
	for(int i=0;i<edge[from].size();i++)
	{
		int to=edge[from][i];
		if(to==pre)
			continue;
		dfs(from,to);
		for(int j=0;j<=c;j++)
			for(int k=0;j+k<=c;k++)
			{
				if(j!=c&&k>0)
					ans=max(ans,dp[from][j][0]+dp[to][k][1]);
				if(k!=c&&j>0)
					ans=max(ans,dp[from][j][1]+dp[to][k][0]);
				if(j+k<c)
					ans=max(ans,dp[from][j][0]+dp[to][k][0]);
				if(j+k<=c)
					ans=max(ans,dp[from][j][1]+dp[to][k][1]);
			}
		for(int j=0;j+trap[from]<=c;j++)
			if(dp[from][j+trap[from]][0]<dp[to][j][0]+w[from])
				dp[from][j+trap[from]][0]=dp[to][j][0]+w[from];
		for(int j=1;j+trap[from]<=c;j++)
			if(dp[from][j+trap[from]][1]<dp[to][j][1]+w[from])
				dp[from][j+trap[from]][1]=dp[to][j][1]+w[from];
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d%d",&n,&c);
		for(int i=0;i<n;i++)
			scanf("%d%d",w+i,trap+i);
		for(int i=0;i<n;i++)
			edge[i].clear();
		while(--n)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			edge[a].push_back(b);
			edge[b].push_back(a);
		}
		ans=0;
		memset(dp,0,sizeof(dp));
		dfs(-1,0);
		cout<<ans<<endl;
	}
}