Pang 居住在一棵有 $n$ 个顶点的树上。顶点编号为 $1, 2, \dots, n$，Pang 最初位于顶点 $1$。每个顶点都有一个温度。在第 $0$ 天之后的每一天早晨，每个顶点的温度都会降低 $1$。第 $0$ 天温度不会降低。每天下午，如果 Pang 所在的顶点温度为正，且目标顶点的温度非负，Pang 可以移动到相邻的顶点。每天晚上，如果当前所在顶点的温度大于或等于 $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$)。

第 $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

1

样例输入 2

3 1
1 2
1 3
2 10 10

样例输出 2

-1