#2581. 苹果树

苹果树

Description

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

Input

输入包含几个测试用例。每个测试用例都包含33部分。第11部分包含两个数字nnkk 11nn 11000000kk 220000,分别表示节点数和所走的步数,节点编号为11nn 。第22部分包含nn 个整数所有整数均非负且不大于11000000,第ii 个整数表示节点ii 的苹果数量。第33部分包含nn -11行,每行都包含两个整数aabb ,表示节点aa 和节点bb 是相邻的。

Output

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

Samples

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

来源

POJ2486