_Pang_ lives on a tree with $n$ vertices. The vertices are labelled as $1, 2, \\dots, n$ and _Pang_ is in vertex $1$. Each vertex has a temperature. On the morning of each day after day 0, the temperature of each vertex decreases by $1$. The temperature doesn't decrease on day 0. On the afternoon of each day, _Pang_ can travel to an adjacent vertex, provided that he is at a vertex with positive temperature and his destination vertex has a non-negative temperature. On the evening of each day, if the temperature is higher than or equal to $0$, _Pang_ can cast magic which increases the temperature of the vertex he is in by $k$. For each pair of adjacent vertices $a$ and $b$, _Pang_ can travel from vertex $a$ to vertex $b$ at most once (and from $b$ to $a$ at most once). He can choose not to travel and stay in the current vertex.
_Pang_ wants to cast his magic on each vertex exactly once. He also tries to stay at vertex $1$ as long as possible, before traveling to any other city. Given the temperature of each vertex right before the morning of the day $1$, on which day must _Pang_ prepare for departing? If _Pang_ prepares on day $i$, he can cast his magic on that day and will make his first move on day $i + 1$. If he cannot cast his magic on each vertex exactly once even if he prepares for departing on the day $0$, output $-1$.
The first line contains two integers $n$ and $k$ ($2 <= n <= 100000, 0 <= k <= 1000000000$).
Each of the next $n -1$ lines contains two integers $x$ and $y$, indicating an edge between vertices $x$ and $y$ ($1 <= x, y <= n$).
The $(n + 1)$-th line contains $n$ integers $a_1, a_2, \\dots, a_n$ — the temperature of vertex $i$ right before the morning of day $1$ ($0 <= a_i <= 1000000000$).
It's guaranteed that the input is a tree structure.
If he cannot cast his magic on each vertex exactly once, output $-1$.
Otherwise, output a single integer $x$ — he must prepare for departing from vertex $1$ on day $x$. Day $1$ is the day after day $0$, and so on.
## Input
The first line contains two integers $n$ and $k$ ($2 <= n <= 100000, 0 <= k <= 1000000000$).Each of the next $n -1$ lines contains two integers $x$ and $y$, indicating an edge between vertices $x$ and $y$ ($1 <= x, y <= n$).The $(n + 1)$-th line contains $n$ integers $a_1, a_2, \\dots, a_n$ — the temperature of vertex $i$ right before the morning of day $1$ ($0 <= a_i <= 1000000000$).It's guaranteed that the input is a tree structure.
## Output
If he cannot cast his magic on each vertex exactly once, output $-1$.Otherwise, output a single integer $x$ — he must prepare for departing from vertex $1$ on day $x$. Day $1$ is the day after day $0$, and so on.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ k \in \mathbb{Z}_{\geq 0} $.
Let $ T = (V, E) $ be a tree with $ V = \{1, 2, \dots, n\} $, $ |V| = n $, and $ 1 \in V $ is the root.
Let $ a_i \in \mathbb{Z}_{\geq 0} $ denote the initial temperature of vertex $ i $ just before morning of day 1.
**State Dynamics**
Let $ t_d(v) $ be the temperature of vertex $ v $ at the start of day $ d $ (before morning decrement).
- $ t_1(v) = a_v $
- For $ d \geq 1 $, before morning of day $ d+1 $: $ t_{d+1}(v) = t_d(v) - 1 $
- On afternoon of day $ d $, Pang may move from $ u $ to $ v $ if $ t_d(u) > 0 $ and $ t_d(v) \geq 0 $, and the edge $ (u,v) $ has not been traversed in either direction.
- On evening of day $ d $, if $ t_d(v) \geq 0 $ and Pang is at $ v $, he may cast magic: $ t_d(v) \leftarrow t_d(v) + k $, **exactly once per vertex**.
**Constraints**
1. Each vertex must be visited and magic cast **exactly once**.
2. Each edge may be traversed **at most once in each direction**.
3. Pang starts at vertex 1 on day 1 (before any action).
4. He must delay departure (first move) as long as possible.
5. Preparation day $ x $: magic can be cast on day $ x $, first move occurs on day $ x+1 $.
**Objective**
Find the minimal day $ x \in \mathbb{Z}_{\geq 0} $ such that:
- Pang can cast magic on all $ n $ vertices exactly once, following movement and temperature constraints,
- He remains at vertex 1 until day $ x $ (i.e., no move before day $ x+1 $),
- If no such $ x $ exists, output $ -1 $.
**Note**: Casting magic on vertex $ v $ requires $ t_d(v) \geq 0 $ at the evening of day $ d $, and the vertex must be visited on day $ d $.