D. 防御
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

提瓦特大陆是一棵树，树上的每个节点从 $$$1$$$ 开始编号，在大陆上的每一个节点中，都有着无尽的知识和宝藏。现在，预言家说，在不久后，在节点 $$$1$$$ 会爆发出一场病毒危机，病毒会沿着树的边不断传播给相邻的节点。假设每一个点都有一个价值 $$$v$$$ 且可以花费 $$$w$$$ 使得该节点无法被感染（包括节点 $$$1$$$）。那么请问，假如可供节点无法被感染的花费总和最大为 $$$c$$$，使用最优的策略，被感染的节点总价值最小是多少？

Input

第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。

对于每组数据：

第一行，两个整数 $$$n,c(2\le n\le 5000;1\le c\le 10^9)$$$，分别代表提瓦特大陆上的节点数和花费的最大值。

第二行，$$$n$$$ 个整数 $$$v_1,\dots,v_n(0\le v_i\le 5000;\sum v\le 5000)$$$，代表每个点的价值。

第三行，$$$n$$$ 个整数 $$$w_1,\dots,w_n(1\le w_i\le 10^9)$$$，代表使得每个点无法被感染的花费。

接下来连续的 $$$n-1$$$ 行，每行两个整数 $$$x,y(1\le x,y\le n)$$$，代表树上的一条边，保证所有的边构成一棵树。

保证同一测试点内 $$$n^2$$$ 和 $$$(\sum v)^2$$$ 的总和均不会超过 $$$5\times 10^7$$$。

Output

对于每组数据，输出一个整数，代表在花费不超过 $$$c$$$ 的情况下，被感染的节点总价值最小是多少。

Example
Input
4
3 10
1 1 1
11 4 5
1 2
1 3
4 9
1 2 3 4
9 10 11 12
1 2
2 3
3 4
11 20
5 27 40 39 47 67 69 75 77 80 30
27 25 24 21 20 19 18 15 5 7 1
1 2
3 2
4 2
1 5
3 7
6 7
7 8
5 9
5 10
11 5
2 1
1 1
2 2
1 2
Output
1
0
315
2