题目描述

可爱的$Wshxzt$非常喜欢苹果。一天，$HX$带她来到一棵苹果树前。这棵树有$N$个节点，每个节点上有一定数量的苹果。$Wshxzt$从节点$1$开始她的快乐采摘之旅，可以吃掉所有到达节点的苹果。

输入格式

• 多组测试数据（以文件结束为终止）
• 每组测试数据包含三部分：
  1. 两个整数$N$ $K$$（1≤N≤100，0≤K≤200）$
  2. $N$个整数，表示每个节点的苹果数量
  3. $N-1$行，每行两个整数$A$ $B$，表示节点$A$和$B$相邻

输出格式

• 对每组测试数据，输出一行最大可获得的苹果数

输入样例1

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

输出样例1

11
2

来源

POJ竞赛，作者：magicpig@ZSU