seuOJ525 - 防御

题目描述

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

输入格式

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

对于每组数据：

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

第二行，nn 个整数 v1,…,vn(0≤vi≤5000;∑v≤5000)v_1,\dots,v_n(0\le v_i\le 5000;\sum v\le 5000)，代表每个点的价值。

第三行，nn 个整数 w1,…,wn(1≤wi≤109)w_1,\dots,w_n(1\le w_i\le 10^9)，代表使得每个点无法被感染的花费。

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

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

输出格式

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

样例

输入样例

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