题目描述

马上就是小苗的生日了，为了给小苗准备礼物，小葱兴冲冲地来到了商店街。商店街有 $n$ 个商店，并且它们之间的道路构成了一棵树的形状。

第 $i$ 个商店只卖第 $i$ 种物品，小苗对于这种物品的喜爱度是 $w_i$，物品的价格为 $c_i$，物品的库存是 $d_i$。但是商店街有一项奇怪的规定：如果在商店 $u,v$ 买了东西，并且有一个商店 $p$ 在 $u$ 到 $v$ 的路径上，那么必须要在商店 $p$ 买东西。小葱身上有 $m$ 元钱，他想要尽量让小苗开心，所以他希望最大化小苗对买到物品的喜爱度之和。

这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为 OI 选手的你，你能帮帮他吗？

输入格式

输入第一行一个正整数 $T$ ，表示测试数据组数。

对于每组数据包含如下 $n+3$ 行：

第一行两个正整数 $n,m$。

第二行 $n$ 个非负整数 $w_1,w_2,\cdots,w_n$。

第三行 $n$ 个正整数 $c_1,c_2,\cdots,c_n$。

第四行 $n$ 个正整数 $d_1,d_2,\cdots,d_n$。

接下来 $n-1$ 行每行两个正整数 $u,v$ 表示 $u$ 和 $v$ 之间有一条道路。

输出格式

输出共 $T$ 行，每行一个整数，表示最大的喜爱度之和。

1
3 2
1 2 3
1 1 1
1 2 1
1 2
1 3

4

数据范围

对于所有数据，保证 $1\leq n\le 500$，$1\le m\le 4000$，$1\le T \le 5$，$0\le w_i\le 4000$，$1 \leq c_i \leq m$，$1\le d_i\le 100$。