Background

很久很久以前，有一只清远鸡由于贪玩不小心走进了一个迷宫当中。

Description

他走遍了迷宫的每个角落，发现这个迷宫实际上是一棵有\( n \)个节点的树形图。他在这棵树的\( 1 \)号节点处发现了\( n \)个踏板,旁边的有一张告示牌，上面写着：“踩下踏板将获得你内心中最想获得的事物，拿走它们你就能离开。”他兴奋地踩下了一个踏板，发现对应编号的节点的相邻节点上出现了米粒，他又踩了下，发现米粒都消失了。经过多次试验，他发现踩下第\( i \)号踏板会改变与\( i \)号节点相邻的所有节点上有无米粒的状态（\( i \)号节点不改变）。已知清远鸡踩下第\( i \)个踏板会失去\( c_i \)点快乐度（踏板太大，清远鸡踩得很难受），吃到第\( i \)号节点上的米粒会先获得\( 2 \)点快乐度，再获得\( 1 \)号节点到\( i \)号节点的距离乘\( 2 \)的快乐度（清远鸡认为越远的越香），每走一条边就会失去\( 1 \)点快乐度。由于清远鸡已经饿得肚子咕咕叫了，所以他最多只能踩下\( w \)个踏板。清远鸡从\( 1 \)号节点出发，最后回到\( 1 \)号节点离开迷宫，且只能在开始时踩下踏板。清远鸡是一只懂得取舍的小鸡，所以他可以选择不把场上出现的全部米粒吃完。现在，清远鸡想知道，他最多能获得多少点快乐度。

Format

Input

第一行两个整数\( n \), \( w \) (\( 1\leq n \leq 50000 \) , \( 1 \leq w \leq 100 \))，表示树的节点数和最多踩下的踏板数。
第二行\( n \)个整数\( c_1 \), \( c_2 \), ... , \( c_n \)(\( 1\leq c_i\leq n \))，表示踩下踏板失去的快乐度。
第三行到第\( n+1 \)行每行两个整数\( u,v \)(\( 1 \leq u,v \leq n \))，表示\( u \)到\( v \)之间有一条边，保证图是一棵树。

Output

输出一行一个整数，表示清远鸡能获得的最大的快乐度。

Sample 1

Input

3 2
1 1 1
1 2
1 3

Output

4

Limitation

2s, 512MB for each test case.
对于10%的数据，保证\( 1 \leq n \leq 20 \)。
对于50%的数据，保证\( 1 \leq n \leq 2000 \)。
对于另外20%的数据，保证\( 1 \leq w \leq 10 \)。
对于100%的数据，保证\( 1 \leq n \leq 50000 \) , \( 1 \leq w \leq 100 \)。

Hint

样例中最优方案下清远鸡踩下\( 1 \)号和\( 2 \)号踏板，此时\( 3 \)个点上均出现米粒，行走路径为\( 1->2->1->3->1 \)，吃到\( 1 \) , \( 2 \)和\( 3 \)处的米粒共得到\( 2+4+4=10 \)点快乐度，有因为走了\( 4 \)的距离所以失去\( 4 \)点快乐度，踩下两个踏板失去\( c_1+c_2=1+1=2 \)点快乐度，总共快乐度为\( 10-4-2=4 \)点。

Source

清远鸡的真实经历