You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

SH的家乡Y市采购了一批先进的通信网络教学用具，用来给中学生演示通信原理。 这种工具有$N$个通信基站和$N-1$条数据链路构成，每个通信基站有一个基本的信号频率$w_i$，每条数据链路连接两个通信基站，保证任何两个基站可以通过数据链路相互到达。 这个通信网络是有一个整体的信号强度$P$的。两个通信基站$u,v$之间能够相互通信，当且仅当： 两个基站的最短路上，经过了至少一个基站$z$，使得基站$z$满足$w_u-w_z\leq P$且$w_v-w_z\leq P$，此处$z$可以等于$u$或者$v$，这样的$z$被称作$u$和$v$的中继基站。注意，一对节点$(u,v)$的中继基站可能有多个。 一个基站的负荷指的是，这个基站承载了多少对基站的通信，也就是说，这个基站是多少个有序对$(u,v)$的中继基站。 现在，请帮助Y市确定一个最大的信号强度$P$，使得每个基站的负荷都小于给定的值$K$。

输入格式

第一行两个整数$N，K$表示基站个数和最大负荷。

接下来一行$N$个整数，表示$w_1~w_N$。

接下来$N-1$行，每行两个整数$u,v$，表示基站$u$和$v$之间存在一条链路。

输出格式

输出仅一个整数，表示最大的$P$，注意，$P$一定是整数，但也许是负数。

4 6
1 2 3 4
1 2
1 3
1 4

2

样例解释

显然2,3,4号点最大负荷只有3，因为只有3对点经过了它。 当P=2的时候，1和4不能通信，所以只能构成(1,2),(1,3),(2,3)一共3对。 当P=3的时候，1和4恢复通信，那么就有C(4,2)=6的负荷了，不满足题意。

大样例在此

数据分布

对于30%的测试数据，满足$1\leq N\leq 1000$（附加样例0，1）

对于70%的测试数据，满足$1\leq N\leq 10^5$（附加样例2）

对于100%的测试数据，满足$1\leq N\leq 3\times 10^5,w_i\leq 10^6,1\leq K\leq N\times (N-1)/2$