Description

一棵虚拟的苹果树有$n$ 个节点，每个节点都有一定数量的苹果。从节点$1$出发，可以吃掉到达节点的所有苹果。当从一个节点转到另一个相邻节点时，需要走一步。计算经过$k$ 步最多吃多少个苹果。

Input

输入包含几个测试用例。每个测试用例都包含$3$部分。第$1$部分包含两个数字$n$、$k$ $（$$1$$≤$$n$ $≤$$1$$0$$0$，$0$$≤$$k$ $≤$$2$$0$$0$$）$，分别表示节点数和所走的步数，节点编号为$1$～$n$ 。第$2$部分包含$n$ 个整数$（$所有整数均非负且不大于$1$$0$$0$$0$$）$，第$i$ 个整数表示节点$i$ 的苹果数量。第$3$部分包含$n$ -$1$行，每行都包含两个整数$a$ 、$b$ ，表示节点$a$ 和节点$b$ 是相邻的。

Output

对每个测试用例，都单行输出经过$k$ 步可以吃到的最大苹果数量。

Samples

2 1
0 11
1 2
3 2
0 1 2
1 2
1 3

11
2