搜集钻石（树形DP经典例题）

搜集钻石（树形DP经典例题）

搜集钻石

Description

蒜国有 n 座城市，编号从 1 到 n，城市间有 n−1 条道路，且保证任意两座城市之间是连通的。每一座城市有一定数量的钻石。

蒜头君想在蒜国搜集钻石。他从城市 1 出发，每天他可以通过城市之间道路开车到另外的城市。当蒜头第一次到一个城市的时候，他可以搜集完这个城市的所有钻石，如果他后面再来到这个城市，就没有砖石可以收集了。

蒜头君只有 K 天时间，请你帮算蒜头君计算他最多可以搜集多少钻石。

Input

第一行输入三个整数 n(1≤n≤100)，K(0≤k≤200)，表示一共有 n 座城市，蒜头君有 K 天时间。

接下里一行输入 n 个用空格隔开的整数，表示每个城市的钻石数量。每个城市的钻石数量不大于 1000。

接下来输入 n−1 行，每行输入两个整数 a(1≤a≤n)，b(1≤b≤n)，表示城市 a和城市 b 之间存在一条双向道路。

Output

输出一行一个整数表示蒜头君最大能获取的钻石数量。

Sample Input 1

3 2
3 8 3
1 3
3 2

Sample Output 1

14

Sample Input 2

6 2
5 9 8