Dungeon of Cards

Time Limit : 5 sec, Memory Limit : 131072 KB

G: Dungeon of Cards / カードの迷宮

物語

ここは不思議の国あじふらい.あじふらい辺境の地に位置するカードの迷宮には,金銀財宝が眠ると伝えられている.好奇心旺盛なあいずにゃんは,この言い伝えを聞くやいなや,友人のウィを連れてカードの迷宮を目指す旅に出ることにした.

翌日,旅の計画を立てるためにあいずにゃんがウィの家を訪れると,ウィは何やら考え込んでいるようだった.どうやら用意周到なウィはカードの迷宮に関する重要な情報を入手したようだ.それは,カードの迷宮には N 枚の扉があり,それぞれの扉を開けるためにカードが必要になるということだ.

カードの迷宮への道中には,扉を開くためのカードを扱う店がある.ウィはここでカードを調達しようと考えているらしいが,問題なのは予算である.あいずにゃんとウィは決してお金持ちではないので,カードにお金をかけすぎてしまうと道中の食料を十分に確保できない可能性があるのだ.

幸い N 枚の扉の情報は,これまで迷宮に挑んだ人々の記録から知ることができた.これなら効率の良いカードの買い方を計算できるかもしれない.しかし,2人で考えるには少し難しい.そこであいずにゃんとウィは,あじふらいに住む優秀なプログラマであるあなたに依頼をすることにした.

問題

N 枚の扉と M 枚のカードがある.扉・カードともに1枚につき英大文字アルファベット ('A'-'Z') 1つと1桁の数字 ('0'-'9') が描かれている.扉にカードをかざすと,カードに描かれたアルファベット,もしくは数字のどちらか一方でも扉のものと一致していれば,その扉を開けることができる.このときカードはなくならないため,同じカードを何度でも使いまわすことができる.また,カードにはそれぞれ値段が付いている.

N 枚の扉と M 枚のカードの情報を元に,すべての扉を開けることができるカードの買い方のうち,要する金額が最小となる場合の金額を計算するプログラムを作成せよ.

入力形式

入力は以下の形式からなる.

 N
 a_1 b_1
 ...
 a_N b_N
 M
 c_1 d_1 e_1
 ...
 c_M d_M e_M

1行目では扉の枚数を表す整数 N が与えられる.続く N 行のうち,i 行目では i 番目の扉に書かれた英大文字アルファベット a_i と1桁の数字 b_i が与えられる.

続く1行では,店で扱われているカードの枚数 M が与えられる.続く M 行のうち,j 行目では j 番目のカードに書かれた英大文字アルファベット c_j と1桁の数字 d_j,価格 e_j が与えられる.

入力は以下の制約を満たす.

  • 1 ≤ N, M ≤ 10{,}000
  • a_i, c_j はアルファベット大文字 ('A'-'Z') 1文字
  • b_i, d_jは1桁の数字 ('0'-'9') 1文字
  • 1 ≤ e_j ≤ 1{,}000
  • N, M, e_j はすべて整数

出力形式

迷宮の扉をすべて開けるために必要なカードを揃えるための最小予算を1行に出力せよ.どのようにカードを買っても全ての扉を開けられない場合,-1を1行に出力せよ.

入力例1

4
D 1
D 2
A 3
D 4
4
A 1 7
D 4 5
D 3 6
B 3 3

出力例1

6

入力例2

4
D 1
D 2
A 3
D 4
4
A 1 7
D 4 5
D 3 10
B 3 3

出力例2

8

入力例3

5
D 1
D 2
A 3
Z 0
D 4
4
A 1 7
D 4 5
D 3 6
B 3 3

出力例3

-1

Source: Ritsumeikan University Programming Camp 2015 , Problem set from Hokkaido University teams, Shiga, Japan, 2015-03-16