問題文

NN 頂点からなる木があり、i (1iN1)i\ (1 \le i \le N-1) 番目の辺は頂点 AiA_i と頂点 BiB_i を結んでいます。また頂点 j (1jN)j\ (1 \le j \le N) には整数 CjC_j が書かれています。
ここで f(u,v)=(f(u,v)=(頂点 uu から頂点 vv への最短パス上の頂点に書かれた数の最大値)) と定義します。
NN 頂点から異なる頂点対 u<vu \lt v を選ぶ方法すべてに対する f(u,v)f(u,v) を求めてそれらを昇順に並べた時、前から KK 番目となる要素を求めてください。

制約

  • 入力はすべて整数
  • 2N2×1052 \le N \le 2 \times 10^5
  • 1KN(N1)21 \le K \le \frac{N(N-1)}{2}
  • 1Ai<BiN1 \le A_i \lt B_i \le N
  • 与えられるグラフは木
  • 1Cj1091 \le C_j \le 10^9

入力

N KN\ K
A1 B1A_1\ B_1
A2 B2A_2\ B_2
\vdots
AN1 BN1A_{N-1}\ B_{N-1}
C1 C2  CNC_1\ C_2\ \dots\ C_N

出力

答えを出力し、最後に改行してください。

入力例1

3 2
1 2
2 3
6 5 4

出力例1

6

f(1,2)=6,f(1,3)=6,f(2,3)=5f(1,2)=6,f(1,3)=6,f(2,3)=5 であるのでこれらを昇順に並べた (5,6,6)(5,6,6)22 番目の要素 66 が答えとなります。

入力例2

5 1
2 4
2 3
1 4
4 5
4 1 3 1 7

出力例2

1

入力例3

9 18
1 5
5 6
4 5
6 9
2 6
5 8
1 3
7 8
19 3 5 17 18 12 6 11 1

出力例3

18

Submit


Go (1.21)