Description

你受邀请参加一个赛车比赛，比赛的规则如下：比赛前，你将收到M万元钱，然后你被送入一个迷宫，必须总终点出来，迷宫内有很多条单行道，还有很多加油站，一开始你的车将被免费加上1L的油，赛道内有很多加油站（包括终点），其中有些是免费的(能提供1L油)，有些是普通加油站，按V元/L的价格卖你一升的油，有些甚至是黑店，收你两倍的钱。从终点出来后，剩余的钱就是你的，当然，如果你花了更多的钱在油费上，也别想拿回来。
比赛前你收到了赛道地图，图上给了你迷宫的起点，终点还有加油站的信息，由于赛道进行过特殊处理，你花费1L的油正好能够从一个加油站开到任一个加油站，那么现在请你考虑下是否参加比赛，如果参加比赛你又能赚到多少钱。

Input

多组数据，每组代表一个赛道。
每组第一行有一个N，V和M，表示有N个加油站，分别标记为0,1,2……N-1，其中，0号为起点，N-1号为终点，普通加油站的汽油价格是V，开始有M万元。然后是两行加油站信息，第二行首先是一个T，表示有T个免费加油站，然后T个数字代表他们的标号数字之间用空格间隔。第三行首先是一个T’,表示有T’个黑店，然后是T’个数字代表黑店标号。
然后是一个数字K，代表有K条单行道，后面有K行，每行包括一个标号a和一个标号b。表示一条a->b的单行道。所有输入数据不超过1000。注意，加油只有三种，没有说明的为普通加油站。

Output

输出你能赚到多少钱，用元做单位，注意当你发现要亏本时，请输出0，因为你没那么苯，你可以选择不参加，一组数据一行。

Sample Input

5 300 1
1 2
1 1
7
0 1
0 3
1 2
1 4
3 2
3 1
2 4

Sample Output

9700

HINT

Source