题目描述

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

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

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

输入格式

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

对于每组数据，

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

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

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

第四行 $n$ 个正整数 $d_1,d_2...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$。

说明

题目来源：BZOJ4182。