#include <bits/stdc++.h>
#define N 20005
#define p 1073741824
using namespace std;
int head[N],tot,son[N],size[N];
int n,m,a[N];
int b[N];
long long ans;
long long dp[20][N];
struct edge{
	int to,nex;
}e[N<<1];
inline void add(int x,int y){
	e[++tot].to=y;
	e[tot].nex=head[x];
	head[x]=tot;
}
void dfs1(int x,int fath){
	size[x]=1; son[x]=0;
	for(int i=head[x];i;i=e[i].nex){
		int to=e[i].to;
		if(to==fath) continue;
		dfs1(to,x); size[x]+=size[to];
		if(size[son[x]]<size[to]) son[x]=to;
	}
}
void dfs(int x,int fa,int o){
	for(int i=m;i>=0;i--) if(i-a[x]>=0) dp[o][i]=max(dp[o][i],dp[o][i-a[x]]+b[x]);
	for(int i=0;i<=m;i++) ans=(ans+((dp[o][i]^(long long)(x)^(long long)(i))%p))%p;
	for(int i=head[x];i;i=e[i].nex){
		int to=e[i].to;
		if(to==fa||to==son[x]) continue;
		for(int j=0;j<=m;j++) dp[o+1][j]=dp[o][j];
		dfs(to,x,o+1);
	}
	if(son[x]!=0) dfs(son[x],x,o);
}
signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	int x,y;
	while(cin>>n>>m){
		memset(head,0,sizeof(head)); tot=0;
		for(int i=1;i<n;i++) cin>>x>>y,add(x,y),add(y,x);
		for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
		dfs1(1,0); memset(dp,0,sizeof(dp)); 
		ans=0; dfs(1,1,0); cout<<ans%p<<endl;
	}
	return 0;
}

题目不重要。可是这一段为什么RE。如果把DP改成int又不RE了QAQ。