自从 Krešo 开始种植辣椒以来，克罗地亚各地的 $N$ 家餐馆都对他的辣椒表现出了兴趣，希望能用真正的香料来丰富他们的菜肴。由于需求量很大，Krešo 决定开始做一名辣椒送货员。

这些餐馆用 $1$ 到 $N$ 的数字表示，并且它们之间通过 $N - 1$ 条道路相互连接，使得任意两家餐馆之间都是连通的。Krešo 从编号为 $1$ 的餐馆开始他的旅程。在一单位时间内，他既可以驾车前往相邻的餐馆，也可以向当前所在的餐馆配送辣椒。对于每家餐馆，我们已知其所需的辣椒数量 $A_i$。

由于送货很累，Krešo 决定总共花费 $M$ 单位的时间用于送货和旅行，之后他计划休息。

求 Krešo 在给定的时间限制内最多可以配送的辣椒总量。你可以假设 Krešo 总是携带无限量的辣椒。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$（$1 \le N, M \le 500$），分别表示餐馆的数量和 Krešo 计划用于配送辣椒的时间。

输入的第二行包含 $N$ 个整数 $A_i$（$1 \le A_i \le 10^6$），表示编号为 $i$（$1 \le i \le N$）的餐馆所需的辣椒数量。

接下来的 $N - 1$ 行，每行包含两个整数 $U$ 和 $V$（$1 \le U, V \le N, U \neq V$），表示餐馆 $U$ 和 $V$ 之间的一条道路。

输出格式

输出 Krešo 在给定的时间限制内最多可以配送的辣椒总量。

样例

输入样例 1

3 5
9 2 5
1 2
1 3

输出样例 1

14

输入样例 2

4 5
1 1 1 2
1 2
2 3
3 4

输出样例 2

3

输入样例 3

5 10
1 3 5 2 4
5 2
3 1
2 3
4 2

输出样例 3

15

说明

样例 1 说明

在第一步中，Krešo 将辣椒配送到餐馆 1。

在第二步中，Krešo 将前往餐馆 3。

在第三步中，Krešo 将辣椒配送到餐馆 3。

此时他还剩下 2 单位的时间，他可以驾车前往餐馆 2，但他缺少 1 单位的时间来向该餐馆配送辣椒。