Shopping

题目描述

马上就是小苗的生日了,为了给小苗准备礼物,小葱兴冲冲地来到了商店街。商店街有 $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

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

输出样例 #1

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 2000$。 #### 说明 题目来源:BZOJ4182。