问题描述

WZland要进行城市规划了。自从上次周年纪念日之后，所有城市以及他们之间的道路构成了一棵树。但城市与城市之间毕竟还是不怎么联系，WZland的居民之间的和谐程度在不断下降，这导致了许多不好的事情发生(比如说犯罪)。为了改善这一状况，WZland的国王决定再一次进行城市规划。

由于N个城市不好控制，WZland的国王决定将这N个城市分成K部分，每个部分构成一个城市联盟。然后国王会亲自指派K个人分别担任这K个城市联盟的领导。 这个问题看似十分简单，但WZland的国王还定下了一些要求：

每个城市联盟里的城市都直接或间接与这一联盟中的其他城市相连接；

设S(i)（1≤i≤K）表示第i个城市联盟的总居民数目，X是最小城市联盟的人数和，即X=min{S(i)|1≤i≤K }。由于城市联盟的人数和这个城市联盟的经济发展速度(人数和经济发展速度成正比，即人数越多经济发展越快)有着千丝万缕的关系，国王他希望经济发展速度最慢的哪个城市联盟的经济发展速度尽量快一些。也就是说国王希望划分方案的X要最大。

现在给你城市之间的道路连接情况以及每个城市的人数，国王要求你告诉他满足他的要求一种划分方案。

输入格式

输入数据第一行包含两个整数N和K，分别表示城市的数目和城市联盟的数目。

第2行到N+1行：第i+1包含一个整数Pi，表示城市i有Pi个居民。

第N+2行到2N行：每行两个整数A和B(1≤A,B≤N，A≠B)，表示城市A和城市B之间有一条道路。

输入数据保证城市之间连接的关系构成一棵树。

输出格式

输出数据只包含一行一个整数X，表示你的划分方案中X值(当然是所有划分方案中最大的X)。

样例输入输出

divide.in

12 3
10
9
1
3
9
9
1
4
6
1
2
3
1 2
2 4
2 5
2 6
4 9
1 3
3 7
3 8
8 10
8 11
8 12

divide.out

10

样例解释

一种可行的划分为：{2,4,5,6,9}、{1,3,7}、{8,10,11,12}（{}内是划分为同一联盟城市）。

数据规模

对于30%的数据，1≤K≤N≤10；

对于50%的数据，1≤K≤N≤1000；

对于100%的数据，1≤K≤N≤20000；

对于100%的数据，Pi≤100000000。