$x$ 个克隆人的军队潜入了“死星”飞船，以帮助卢克·天行者对抗达斯·维达。这艘飞船由 $n$ 个房间和 $m$ 条连接它们的双向通道组成。克隆人从 1 号房间出发，想要到达卢克所在的 $n$ 号房间。

然而，每个房间都有机器人守卫，其中 $i$ 号房间由 $a_i$ 个机器人守卫。当克隆人出现在房间时，他们与机器人之间的战斗就会开始。如果克隆人的数量大于机器人的数量，克隆人将消灭所有机器人，且所有克隆人都会存活。否则，克隆人同样会消灭所有机器人，但他们会损失一半的军队：如果战斗开始时有 $x$ 个克隆人，那么战斗结束后将剩下 $\lfloor \frac{x}{2} \rfloor$ 个克隆人。克隆人必须在他们经过的所有房间进行战斗，包括 1 号房间和 $n$ 号房间。

请帮助军队指挥官计算从 1 号房间到达 $n$ 号房间时，能够存活下来的克隆人的最大数量。

输入格式

第一行包含两个整数 $n$ 和 $m$ —— “死星”中房间和通道的数量 ($1 \le n, m \le 2 \cdot 10^5$)。

接下来的 $m$ 行描述通道：第 $i$ 条通道由两个整数 $u_i$ 和 $v_i$ 描述 —— 通道连接的房间 ($1 \le u_i, v_i \le n, u_i \neq v_i$)。保证每对房间之间最多只有一条通道。

下一行包含一个整数 $x$ —— 军队中克隆人的数量 ($1 \le x \le 10^9$)。

最后一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ —— 各房间中机器人的数量 ($1 \le a_i \le 10^9$)。

输出格式

输出一个整数 —— 从 1 号房间到达 $n$ 号房间时，能够存活下来的克隆人的最大数量。如果没有路径可以使至少一名克隆人存活，则输出 0。

样例

样例输入 1

4 4
1 2
1 3
2 4
3 4
7
10 2 3 1

样例输出 1

3

样例输入 2

4 4
1 2
1 3
2 4
3 4
7
10 3 3 1

样例输出 2

0