Description

There is a tree with n nodes.Each node have a weight which is a positive number. A tree's weight is the sum of its nodes' weight. You can divide the tree into k parts,each part is still a tree. A divide have a weight,which is the minimum of the k subtrees. Can you tell me the maximum of divide?

Input

The input contains several testcases. For each testcase,the first line is n and k. The following one line which contain n number,describe the weight of each node. The following n-1 lines contain p and q,which describe that there is an edge between p and q. (1 <= k <= n <= 50000 0 <= p,q <= n-1 1 <= weight <= 100000000)

Output

For each test case print one line,which is the maximum.

Sample Input

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

Sample Output

10

Author

windy7926778
Best wishes to scu07t01 Special for myself from rank2 to rank1 in soj on oct 3,2007 by Solved 1178 and Submitted 3304