불

Pang은 정점이 $n$개인 트리에 살고 있다. 정점은 $1, 2, \ldots, n$으로 번호가 붙어 있고, Pang은 정점 $1$에 있다. 각 정점에는 온도가 있다. 0일 이후 매일 아침마다 모든 정점의 온도가 $1$씩 내려간다. 0일에는 온도가 내려가지 않는다. 매일 오후, Pang은 인접한 정점으로 이동할 수 있다. 단, 현재 정점의 온도가 양수이고 목적지 정점의 온도가 0 이상이어야 한다. 매일 저녁, 현재 정점의 온도가 0 이상이면 Pang은 그 정점의 온도를 $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$) 마지막 줄에는 1일 아침 직전의 정점 $i$ 온도 $a_1, a_2, \ldots, a_n$이 주어진다. ($0 \le a_i \le 1000000000$) 입력은 트리임이 보장된다.

Pang이 각 정점에서 마법을 정확히 한 번씩 쓸 수 없다면 $-1$을 출력한다. 그렇지 않으면 Pang이 정점 $1$에서 출발 준비를 해야 하는 날 $x$를 한 정수로 출력한다. 1일은 0일 다음 날이다.