Prof. Pang 沉迷于一款名为《艾尔登法环》（Elden Ring）的游戏。游戏世界是一个包含 $n$ 个顶点（编号从 $1$ 到 $n$）和 $m$ 条无向边的连通图。玩家从顶点 $1$ 出发，在世界中旅行，目标是击败位于顶点 $n$ 的神。

然而，这并不容易。对于除顶点 $1$ 以外的任何顶点 $i$，都有一个等级为 $l_i$ 的 Boss，玩家初始等级为 $l_1$。每天，玩家可以从顶点 $1$ 出发前往任意顶点 $i$ 并挑战那里的 Boss。如果玩家当前的等级高于 Boss 的等级，该 Boss 将被从世界中消除（失活），且玩家的等级会增加 $A$。注意，经过有活跃 Boss 的顶点是被禁止的。（换句话说，Prof. Pang 可以从顶点 $1$ 前往顶点 $i$，当且仅当图中存在一条从顶点 $1$ 到顶点 $i$ 的路径，使得该路径上除顶点 $i$ 以外的每个顶点都没有活跃的 Boss。）同时，在每天开始时，世界中所有剩余的 Boss 等级都会提升 $B$。

为了通关游戏，你需要击败位于顶点 $n$ 的 Boss（艾尔登之兽）。给定世界的信息，Prof. Pang 想知道他最少需要多少天才能完成任务。

玩家每天只能挑战一个 Boss。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含四个整数 $n, m, A, B$ ($2 \le n \le 2 \times 10^5, 1 \le m, A, B \le 2 \times 10^5$)。

接下来的 $m$ 行，每行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n$)，表示第 $i$ 条无向边的两个端点。最后一行包含 $n$ 个整数 $l_i$ ($1 \le l_i \le 2 \times 10^5$)，分别表示玩家的初始等级和各顶点的 Boss 等级。

保证所有测试用例的 $n$ 之和不超过 $10^6$，所有测试用例的 $m$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行一个整数，表示 Prof. Pang 完成游戏所需的最少天数。如果无法完成，请输出 $-1$。

样例

输入 1

2
5 4 5 8
1 2
1 3
1 4
4 5
15 1 1 1 1
5 4 10 5
1 2
1 3
1 4
4 5
10 4 4 4 19

输出 1

2
4