012 - adventure

問題

あなたはモンスターが潜むダンジョンに挑む冒険者です。このダンジョンには複数の部屋があり、それらは通路でつながっています。あなたの目的は、部屋$0$から部屋$N$まで、できるだけ少ないターンで到達することです。ただし、一部の部屋にはモンスターが潜んでおり、モンスターを倒さない限りその部屋を通り抜けることはできません。モンスターは体力を0以下にすることで倒すことができます。

1ターンでできることは以下の２つです。
・通路でつながっている隣の部屋に移動する。
・同じ部屋にいるモンスターの体力を$A$だけ減らす。

また、到達できない場合は-1を出力してください。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $A$
$U_1$ $V_1$
$U_2$ $V_2$
 :
$U_M$ $V_M$
$Q$
$P_1$ $H_1$
$P_2$ $H_2$
 :
$P_Q$ $H_Q$

１行目にダンジョンの部屋の数$N$,ダンジョンの通路の数$M$,攻撃力$A$が与えられる。
続く$M$行にわたって、通路についての情報が与えられる。
$U_i$ $V_i$は部屋$U_i$と部屋$V_i$が通路$i$によって互いに行き来可能なことを表す。
$M+2$行目にダンジョンに存在するモンスターの数$Q$が与えられる。
続く$Q$行にわたって、モンスターの情報が与えられる。
$P_i$ $H_i$は体力が$H_i$のモンスター$i$が部屋$P_i$にいることを示す。

出力

出力の最後に改行を入れること。

制約

全ての入出力ケースについて以下を満たす。

• $1 \leq N,M \leq 10^{6}$
• $0 \leq A,H_i \leq 10^{9}$
• $1 \leq U_i,V_i \leq N$
• $2 \leq P_i \leq N-1$
• $U_i \ne V_i$
• $P_i \ne P_j(i \ne j)$
• $0 \leq Q \leq N-2$
• 入力はすべて整数

部分点

部分点1は以下の制約を満たす。(点数の20%)

$Q = 0$

入出力例

入力例1

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

出力例1

4

１ターン目 : 部屋１から部屋２に移動
２ターン目 : 部屋2にいるモンスターに攻撃
３ターン目 : 部屋2にいるモンスターに攻撃
４ターン目 : 部屋2から部屋5に移動

入力例2

6 6 2
1 2
1 3
2 6
3 4
4 5
5 6
1
2 9

出力例2

4

回り道をしてモンスターを避けるのが最適です。

入力例2

6 4 10000
1 2
2 3
3 4
4 5
4
2 999
3 999
4 999
5 999

出力例2

-1

そもそもたどり着けません。