Pang mieszka na drzewie o $n$ wierzchołkach. Wierzchołki są ponumerowane od $1, 2, \dots, n$, a Pang znajduje się w wierzchołku $1$. Każdy wierzchołek ma określoną temperaturę. Rankiem każdego dnia po dniu $0$, temperatura każdego wierzchołka maleje o $1$. Temperatura nie maleje w dniu $0$. Po południu każdego dnia Pang może przemieścić się do sąsiedniego wierzchołka, pod warunkiem, że znajduje się w wierzchołku o dodatniej temperaturze, a wierzchołek docelowy ma nieujemną temperaturę. Wieczorem każdego dnia, jeśli temperatura wierzchołka, w którym przebywa Pang, jest większa lub równa $0$, może on użyć magii, która zwiększa temperaturę tego wierzchołka o $k$. Dla każdej pary sąsiednich wierzchołków $a$ i $b$, Pang może przemieścić się z wierzchołka $a$ do $b$ co najwyżej raz (oraz z $b$ do $a$ co najwyżej raz). Może również zdecydować się nie podróżować i pozostać w obecnym wierzchołku.

Pang chce użyć swojej magii w każdym wierzchołku dokładnie raz. Stara się również pozostać w wierzchołku $1$ tak długo, jak to możliwe, zanim wyruszy do jakiegokolwiek innego miasta. Mając dane temperatury każdego wierzchołka tuż przed porankiem dnia $1$, określ, którego dnia Pang musi przygotować się do wyjazdu. Jeśli Pang przygotuje się w dniu $i$, może użyć magii tego dnia i wykona swój pierwszy ruch w dniu $i + 1$. Jeśli nie jest w stanie użyć magii w każdym wierzchołku dokładnie raz, nawet jeśli przygotuje się do wyjazdu w dniu $0$, wypisz $-1$.

Wejście

Pierwsza linia zawiera dwie liczby całkowite $n$ oraz $k$ ($2 \le n \le 100000$, $0 \le k \le 1000000000$).

Każda z kolejnych $n - 1$ linii zawiera dwie liczby całkowite $x$ oraz $y$, oznaczające krawędź między wierzchołkami $x$ oraz $y$ ($1 \le x, y \le n$).

$(n + 1)$-sza linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ — temperaturę wierzchołka $i$ tuż przed porankiem dnia $1$ ($0 \le a_i \le 1000000000$).

Gwarantuje się, że struktura wejściowa jest drzewem.

Wyjście

Jeśli Pang nie jest w stanie użyć magii w każdym wierzchołku dokładnie raz, wypisz $-1$.

W przeciwnym razie wypisz pojedynczą liczbę całkowitą $x$ — dzień, w którym Pang musi przygotować się do wyjazdu z wierzchołka $1$. Dzień $1$ to dzień następujący po dniu $0$, i tak dalej.

Przykład

Wejście 1

3 1
1 2
1 3
4 3 5

Wyjście 1

1

Wejście 2

3 1
1 2
1 3
2 10 10

Wyjście 2

-1