3862: 【CSP2022】肥尔登法环

game.in/out

小V在游玩新游《肥尔登法环》，肥尔登法环的世界由N-1个boss房和1个初始篝火组成，M条无向的通道连接着这N个地点。地图的1号点表示初始篝火，第2-N号点里面各有一个Boss。

每天，小V可以从初始篝火出发，去讨伐一个Boss并且返回篝火。当一个Boss被击败了，他就会永久从地图上消失。小V每天只能讨伐一个Boss，所以在他前去讨伐目标的路上，不能碰到其他敌人。

Boss的难度各有不同，小V只能战胜那些等级严格低于他的Boss，小V的初始等级是L1，2-N号点里面的Boss等级依次是L2-LN。小V每战胜一个Boss，等级都会上升A，然而不幸的是，每天的开始（包括第一天），Boss都会变强，等级上升B。(保证A>B)

小V的目标是，战胜位于N号点的大Boss塔塔露以通关，他想知道，他能否完成这个目标，如果能，输出他只少需要多少天通关，如果不能，输出-1。

【数据规模和约定】
对于50%的数据 N<=10
对于 100%的数据的数据 N<=50000 M<=1e6

T<=10  A,B<=5000   Li<=10000

第一行一个数T 表示有T组数据

对于每组数据

第一行4个数 N M A B

接下来M行，每行两个数 表一条边

接下来一行N个数 表示L1-LN

T行，每行一个数，表答案

3
5 4 10 5
1 2
1 3
1 4
4 5
10 4 4 4 19
5 5 1 0
1 2
1 3
3 4
2 5
4 5
10 100 1 1 11
5 4 1 0
1 2
3 1
1 4
5 1
2 1 3 3 4

4
3
-1