Wrought Gold Master

Time Limit : 1 sec, Memory Limit : 65536 KB

Wrought Gold Master

錬金マスター

勇者はついに魔法の釜、錬金釜を手に入れました。錬金釜に複数のアイテムを入れると、新しいア イテムを作ることができます。新しく作ったアイテムは、他のアイテムを作るために錬金釜へ入れる こともできます。アイテムを作るために必要なアイテムのリストを記したものを錬金レシピと呼ぶこ とにします。以下の 3 つは錬金レシピの例です。

  1. 木片と糸でラケットができる。
  2. お米と水でおにぎりができる。
  3. ラケットとマイクとおにぎりでギターができる。

アイテムはお金を使って手にいれることもできますが、錬金釜で作った方が安くすむ場合もありま す。例えば、各アイテムの購入価格が図 1 のように与えられているとします。

アイテム名 購入価格(円)
木片 3,000
800
お米 36
0
ラケット 5,000
マイク 9,800
おにぎり 140
ギター 98,000

図 1

ラケットは 5,000 円で購入できますが、木片と糸を購入して錬金すれば 3,800 円で手に入れられ ます。更に、錬金を重ねることによりとてもお得にアイテムを手に入れられます。図 2 は上記 3 つ の錬金レシピ例を組み合わせたものです。ギターは 98,000 円で購入できますが、木片、糸、お米、 水、マイクを購入して錬金すれば、たったの 13,636 円で手に入れられます。



図 2



勇者は冒険を楽に進めるため、なるべく安く目的のアイテムを手に入れようと考えました。 アイテムのリスト、錬金レシピのリスト、指定されたアイテムを入力とし、指定されたアイテムを 作るために必要な金額の最小値を出力するプログラムを作成して下さい。

アイテムリストに含まれるアイテムの種類 n は 1 以上 100 以下の整数とし、 各アイテムを購入す る場合の値段 p は 0 以上 1000000 以下とします。アイテムの名前 i は 1 文字以上 100 文字以下 のアルファベットからなる半角文字列です。 錬金レシピの種類 m は 0 以上 100 以下の整数です。 1 つの錬金レシピはアイテムの名前 o 、それを作るために必要なアイテムの個数 k 、 k 個のアイテム 名 q のリストによって与えられます。k は 100 以下とします。

各アイテムの数量に限りはないものとします。アイテムは複数のレシピに使われることがあります が、1 つのアイテムを作るためのレシピはたかだか 1 つです。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されま す。各データセットは以下のとおりです。

1 行目 リストに含まれるアイテムの数 n (整数)
2 行目 第 1 のアイテムの情報 i p (半角文字列 整数;半角空白区切り)
3 行目 第 2 のアイテムの情報
        :
n+1 行目 第 n のアイテムの情報
n+2 行目 錬金レシピの数 m (整数)
n+3 行目 第 1 の錬金レシピの情報 o k q1 q2 ・・・ qk
(半角文字列 整数 半角文字列 ・・・ 半角文字列;半角空白区切り)
n+4 行目 第 2 の錬金レシピの情報
        :
n+m+2 行目 第 m の錬金レシピの情報
n+m+3 行目 指定されたアイテム名 (半角文字列)

Output

入力データセットごとに、最小の値段を出力します。

Sample Input

8
wood 3000
string 800
rice 36
water 0
racket 5000
microphone 9800
onigiri 140
guitar 98000
3
racket 2 wood string
onigiri 2 rice water
guitar 3 racket microphone onigiri
guitar
1
computer 300000
0
computer
0

Output for the Sample Input

13636
300000

Source: PC Koshien 2009, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2009
http://www.pref.fukushima.jp/pc-concours/