An old country has n cities, which are numbered from 1 to N. Cities are connected by road, and there is exact one path between two different cities.In order to manage the country, the king decide to divide the country into k regions,each region may contain several citys, and all the cities of a region can get to the other cities in this region by only through cities of the region.We can think that the number of the residents of city i is X_i , and the King wants to make the number of resident of evevy region as large as possible(equal means the least number as large as possible).As his most intelligent minister,can you help the King to divid the regions?

The first line contains two integer N ( 0 < N ≤ 10000) and k( k ≤ N ), means the number of citiy and the number of  region.the second line contains N inerger X_i ( 1 ≤ X_i ≤ 100 ),means the number of residents of city i, then the flowing n-1 lines,u,v (1 ≤ u, v ≤ N) ,which means the is a road between city u and city v.

Output the largest number of resident that every region can have.