問題
あなたはモンスターが潜むダンジョンに挑む冒険者です。このダンジョンには複数の部屋があり、それらは通路でつながっています。あなたの目的は、部屋$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%)
入出力例
入力例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
そもそもたどり着けません。