For his computer science class, Jacob builds a model tree with sticks and balls containing n nodes in the shape of a tree. Jacob has spent a_i minutes building the i-th ball in the tree.

Jacob's teacher will evaluate his model and grade Jacob based on the effort he has put in. However, she does not have enough time to search his whole tree to determine this; Jacob knows that she will examine the first k nodes in a DFS-order traversal of the tree. She will then assign Jacob a grade equal to the minimum a_i she finds among those k nodes.

Though Jacob does not have enough time to rebuild his model, he can choose the root node that his teacher starts from. Furthermore, he can rearrange the list of neighbors of each node in any order he likes. Help Jacob find the best grade he can get on this assignment.

A DFS-order traversal is an ordering of the nodes of a rooted tree, built by a recursive DFS-procedure initially called on the root of the tree. When called on a given node v, the procedure does the following:

1. Print v.
2. Traverse the list of neighbors of the node v in order and iteratively call DFS-procedure on each one. Do not call DFS-procedure on node u if you came to node v directly from u.

The first line of the input contains two positive integers, n and k (2≤n≤200000, 1≤k≤n)− the number of balls in Jacob's tree and the number of balls the teacher will inspect.

The second line contains n integers, a_i (1≤a_i≤1000000), the time Jacob used to build the i-th ball.

Each of the next n-1 lines contains two integers u_i, v_i (1≤u_i,v_i≤n, u_i≠v_i) representing a connection in Jacob's tree between balls u_i and v_i.

Print a single integer− the maximum grade Jacob can get by picking the right root of the tree and rearranging the list of neighbors.