Shopping

Time Limit : 1 sec, Memory Limit : 65536 KB

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

Source: Ritsumeikan University Programming Camp 2015 , Day 1, Shiga, Japan, 2015-03-14