Pang は $n$ 個の頂点からなる木の上に住んでいる。頂点には $1, 2, \dots, n$ のラベルが付けられており、Pang は頂点 $1$ にいる。各頂点には温度が設定されている。0日目以降の毎朝、各頂点の温度は $1$ ずつ減少する。0日目には温度は減少しない。毎日の午後、Pang は現在いる頂点の温度が正であり、かつ移動先の頂点の温度が $0$ 以上であれば、隣接する頂点へ移動することができる。毎日の夕方、現在いる頂点の温度が $0$ 以上であれば、Pang は魔法を使って現在いる頂点の温度を $k$ 増やすことができる。隣接する頂点の各ペア $(a, b)$ について、Pang は頂点 $a$ から頂点 $b$ へ最大 $1$ 回まで移動できる（$b$ から $a$ へも最大 $1$ 回まで）。移動せずにその場にとどまることもできる。

Pang は各頂点でちょうど $1$ 回ずつ魔法を使いたいと考えている。また、他の都市へ移動する前に、できるだけ長く頂点 $1$ にとどまりたいと考えている。1日目の朝の直前における各頂点の温度が与えられたとき、Pang は何日目に出発の準備をしなければならないか。$i$ 日目に出発の準備をする場合、その日に魔法を使うことができ、翌日の $i+1$ 日目に最初の移動を行う。0日目に出発の準備をしたとしても各頂点でちょうど $1$ 回ずつ魔法を使うことができない場合は、$-1$ を出力せよ。

入力

入力の最初の行には、2つの整数 $n$ と $k$ ($2 \le n \le 100000, 0 \le k \le 1000000000$) が含まれる。

続く $n-1$ 行の各行には、頂点 $x$ と $y$ の間の辺を表す2つの整数 $x$ と $y$ ($1 \le x, y \le n$) が含まれる。

$(n+1)$ 行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ が含まれる。これは1日目の朝の直前における頂点 $i$ の温度である ($0 \le a_i \le 1000000000$)。

入力が木構造であることは保証されている。

出力

各頂点でちょうど $1$ 回ずつ魔法を使うことができない場合は、$-1$ を出力せよ。

そうでない場合、単一の整数 $x$ を出力せよ。これは、Pang が頂点 $1$ から出発するために準備をしなければならない日である。1日目は0日目の翌日であり、以降同様である。

入出力例

入力 1

3 1
1 2
1 3
4 3 5

出力 1

1

入力 2

3 1
1 2
1 3
2 10 10

出力 2

-1