D. 防御

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

第一行，一个整数 $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$。

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

输入样例

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

输出样例

1
0
315
2