C : Shopping / 買い物
問題文
料理が得意な2D君は昼ごはんを作ろうとしている。料理には N 個の材料 a_{0}, a_{1}, … , a_{N−1} が全てが必要である。
さて、今2D君の家の冷蔵庫には一つも材料が入っていないので、スーパーに買いに行かなければならない。スーパーでは材料 a_{i} を値段 x_{i} 円で買うことができる。
2D君は魔法使いでもあり、 M 種類の魔法が使える。 i 番目の魔法を材料 s_{i} にかければ材料 t_{i} に、また逆に t_{i} にかければ s_{i} に変えることができる。さらに、一つの材料に対して複数の魔法を繰り返して使うことができる。例えば、 p から q に変える魔法と、 q から r に変える魔法の2つを使って、 p から r を得ることができる。
2D君は魔法の力を借りてなるべく安く材料を揃えることにした。料理を完成させるために2D君が買う必要のある材料の、値段の総和の最小値を求めよ。
入力
入力は以下の形式で与えられる。
N
a_{0} x_{0}
…
a_{N−1} x_{N−1}
M
s_{0} t_{0}
…
s_{M−1} t_{M−1}
制約
- 数値はすべて整数である
- 材料の名前はすべて 1 文字以上 10 文字以下のアルファベット小文字からなる
- i ≠ j なら a_{i} ≠ a_{j}
- 1 \≤ x_{i} \≤ 1,000
- 1 \≤ N \≤ 5,000
- 0 \≤ M \≤ {\rm min}(N(N−1)/2, 1000)
- s_{i} ≠ t_{i}
- s_{i},t_{i} の組に重複はない
- s_{i},t_{i} は a_{0},…,a_{N−1} に含まれる
出力
答えを1行で出力せよ。
サンプル
サンプル入力1
2 tako 2 yaki 1 1 tako yaki
魔法によって安い yaki を tako に変えることができるので、 yaki を 2 個買えばよい。
サンプル出力1
2
サンプル入力2
5 a 1 b 2 c 2 d 4 e 3 5 b a a c c d e b c b
サンプル出力2
5
下に示すように、全ての材料を a から変えてそろえることができる。
- a : a そのまま
- b : a -> c -> b
- c : a -> c
- d : a -> c -> d
- e : a -> b -> e
