#4182. Shopping

内存限制:128 MiB 时间限制:30 Sec

题目描述

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

第i个商店只卖第i种物品,小苗对于这种物品的喜爱度是wi,物品的价格为ci,物品的库存是di。但是商店街有一项奇怪的规定:如果在商店u,v买了东西,并且有一个商店w在u到v的路径上,那么必须要在商店w买东西。小葱身上有m元钱,他想要尽量让小苗开心,所以他希望最大化小苗对买
到物品的喜爱度之和。这种小问题对于小葱来说当然不在话下,但是他的身边没有电脑,于是他打电话给同为OI选手的你,你能帮帮他吗?

输入格式

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

对于每组数据,
第一行两个正整数n;m;
第二行n个非负整数w1,w2...wn;
第三行n个正整数c1,c2...cn;
第四行n个正整数d1,d2...dn;
接下来n-1行每行两个正整数u;v表示u和v之间有一条道路

输出格式

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

样例

样例输入


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

样例输出


			
4

数据范围与提示

 N<=500,M<=4000,T<=5,Wi<=4000,Di<=100