問題文


頂点からなる木があり、 番目の辺は頂点 と頂点 を結んでいます。また頂点 には整数 が書かれています。
ここで 頂点 から頂点 への最短パス上の頂点に書かれた数の最大値 と定義します。
頂点から異なる頂点対 を選ぶ方法すべてに対する を求めてそれらを昇順に並べた時、前から 番目となる要素を求めてください。

制約


  • 入力はすべて整数
  • 与えられるグラフは木

入力







出力


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

入力例1

3 2
1 2
2 3
6 5 4
出力例1

6

であるのでこれらを昇順に並べた 番目の要素 が答えとなります。

入力例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.14)