Панг живет в дереве с $n$ вершинами. Вершины пронумерованы от $1$ до $n$, Панг находится в вершине $1$. У каждой вершины есть температура. Утром каждого дня, начиная с дня после дня $0$, температура каждой вершины уменьшается на $1$. В день $0$ температура не уменьшается. Днем Панг может переместиться в соседнюю вершину при условии, что он находится в вершине с положительной температурой, а температура вершины назначения неотрицательна. Вечером каждого дня, если температура вершины, в которой находится Панг, больше или равна $0$, он может применить магию, которая увеличивает температуру этой вершины на $k$. Для каждой пары соседних вершин $a$ и $b$ Панг может переместиться из $a$ в $b$ не более одного раза (и из $b$ в $a$ не более одного раза). Он может выбрать не перемещаться и остаться в текущей вершине.

Панг хочет применить свою магию в каждой вершине ровно один раз. Он также старается оставаться в вершине $1$ как можно дольше, прежде чем отправиться в любой другой город. Даны температуры каждой вершины непосредственно перед утром дня $1$. Определите, в какой день Панг должен начать подготовку к отъезду. Если Панг начинает подготовку в день $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$ — день, в который он должен начать подготовку к отъезду из вершины $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