题号：NC214798
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
Bear_2最近迷上了圆神，其中有一副本有 n 个关卡由 n-1 条边连接(保证一定联通)。简单起见每个关卡编号为 1-n，起点为 1 号关卡。 第 i 号关卡的怪物数量为 Ai 。每条边只能走两次，走过一条边的时间忽略，在每个关卡停留时间为1秒(不管多少怪全秒) ，不允许中途停留 。 每个关卡的怪物隔 t(1<t<10) 秒刷新(假设在 x 秒的时候清过一次怪，则在 x+t 秒时刷新)。 Bear_2每次从1号点进入副本，再从1号关卡退出副本，请问最多能清多少怪。 保证，每个关卡的度数不会超过10.
输入描述:
第一行输入两个正整数 n,t(1<=n<=103,1<=t<=10)
第二行输入n个正整数，第i个正整数 Ai (1<=Ai<=103)表示第i个关卡的怪物数量
之后的n-1行，每行给出两个正整数 A,B ，表示关卡A与关卡B之间有一条通路。
输出描述:
在一行内输出清除怪物的最大数量
示例1
输入
复制
9 9
2 2 7 2 9 2 2 10 5
6 4
9 3
4 1
1 5
2 7
8 7
1 2
9 5