Pang 居住在一棵有 $n$ 個頂點的樹上。頂點編號為 $1, 2, \dots, n$，且 Pang 起始位於頂點 $1$。每個頂點都有一個溫度。在第 $0$ 天之後的每一天早晨，每個頂點的溫度都會減少 $1$。第 $0$ 天時溫度不會減少。在每一天的下午，若 Pang 所在的頂點溫度為正，且目標頂點的溫度為非負，則 Pang 可以移動到相鄰的頂點。在每一天的晚上，若 Pang 所在頂點的溫度大於或等於 $0$，他可以施展魔法，使其所在頂點的溫度增加 $k$。對於每一對相鄰頂點 $a$ 和 $b$，Pang 最多只能從 $a$ 移動到 $b$ 一次（且從 $b$ 移動到 $a$ 也最多一次）。他也可以選擇不移動，停留在當前的頂點。

Pang 想要在每個頂點上各施展一次魔法。他同時也希望在前往其他城市之前，盡可能長時間地停留在頂點 $1$。給定每個頂點在第 $1$ 天早晨之前的溫度，Pang 必須在第幾天準備出發？若 Pang 在第 $i$ 天準備出發，他可以在當天施展魔法，並在第 $i+1$ 天進行第一次移動。若即使在第 $0$ 天準備出發也無法在每個頂點上各施展一次魔法，則輸出 $-1$。

輸入格式

第一行包含兩個整數 $n$ 和 $k$ ($2 \le n \le 100000, 0 \le k \le 1000000000$)。

接下來的 $n-1$ 行，每行包含兩個整數 $x$ 和 $y$，表示頂點 $x$ 和 $y$ 之間有一條邊 ($1 \le x, y \le n$)。

第 $n+1$ 行包含 $n$ 個整數 $a_1, a_2, \dots, a_n$，代表頂點 $i$ 在第 $1$ 天早晨之前的溫度 ($0 \le a_i \le 1000000000$)。

保證輸入結構為一棵樹。

輸出格式

若他無法在每個頂點上各施展一次魔法，輸出 $-1$。

否則，輸出一個整數 $x$ — 他必須在第 $x$ 天準備從頂點 $1$ 出發。第 $1$ 天是第 $0$ 天之後的那一天，以此類推。

範例

範例 1

3 1
1 2
1 3
4 3 5

1

範例 2

3 1
1 2
1 3
2 10 10

-1