#2643. 餐馆

餐馆

题目描述

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

输入格式

第一行有两个正整数N\red{N,}M\red{M}

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

接下来有N1\red{N-1}行描述道路的情况,每行两个正整数u\red{u,}v\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

提示

对于10%\red{10\%}的数据,N\red{N≤}20\red{20}

对于50%\red{50\%}的数据,N\red{N≤}110\red{110}

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

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

样例1\red{1}解释

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