题目描述

$\red{K}$妹的胡椒粉大卖，这辣味让食客们感到刺激，许多餐馆也买这位$\red{K}$妹的账。有$\red{N}$家餐馆，有$\red{N-1}$条道路，这$\red{N}$家餐馆能相互到达。$\red{K}$妹从$\red{1}$号餐馆开始。每一个单位时间，$\red{K}$妹可以在所在餐馆卖完尽量多的胡椒粉，或者移动到有道路直接相连的隔壁餐馆。第$\red{i}$家餐馆最多需要$\red{A[i]}$瓶胡椒粉。$\red{K}$妹有$\red{M}$个单位的时间，问她最多能卖多 少胡椒粉。

输入格式

第一行有两个正整数$\red{N，}$$\red{M}$。

第二行描述餐馆对胡椒粉的最大需求量，有$\red{N}$个正整数，表示$\red{A[i]}$。

接下来有$\red{N-1}$行描述道路的情况，每行两个正整数$\red{u，}$$\red{v，}$描述这条道路连接的两个餐馆。

输出格式

一个整数，表示她最多能卖的胡椒粉瓶数。

样例

输入样例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

提示

对于$\red{10\%}$的数据，$\red{N≤}$$\red{20}$。

对于$\red{50\%}$的数据，$\red{N≤}$$\red{110}$。

对于$\red{100\%}$的数据$\red{1 ≤}$ $\red{N, M ≤}$ $\red{500，}$$\red{1 ≤}$ $\red{A[i]≤}$ $\red{10^6，}$

第$\red{5}$到第$\red{10}$个测试点都有多个子测试。

样例$\red{1}$解释

在样例$\red{1}$的中，辣妹到达城市$\red{2}$后就恰好没时间卖辣椒粉了。