English text is not available in this practice contest.

時は XXXX 年。戦乱の世である。

土地や資源を巡って、隣り合った国同士の衝突がそこかしこで起こり、世の中の先行きは非常に不透明であった。そんな中とある国が、様々な国と軍事同盟を結んでこの乱世を生き延びようと考えた。軍事同盟は次の条件をみたすように行うことが出来る。

• 自国の隣国とは同盟を結ぶことは出来ない。
• 同盟をした国の隣国とは同盟を結ぶことは出来ない。

ただし、国ごとにその軍事的な強さは異なっている。軍事的に強くない複数の国と同盟を結ぶより、軍事的に非常に強い一国と同盟を結んだほうが有利であることも有り得る。ここでは、同盟に含まれる国の軍事的強さの和が最大になるような軍事同盟の結び方を考えたい。

入力は複数のデータセットからなる．各データセットの形式は次の通りである。

N
A₁ B₁ C₁ D_1,1... D_1,C1
A₂ B₂ C₂ D_2,1... D_2,C2
...
A_N B_N C_N D_N,1... D_N,CN

各データセットでは、1行目は国の数 N (1 ≤ N ≤ 40)が与えられ、2〜N+1行目には国の詳細が与えられる。国の詳細では、国名 A_i、軍事的強さ B_i 、隣接している国の数 C_i、隣接している国のリスト D_i,1... D_i,Ci が与えられる。自国は1つ目の国 A₁ である。

国名 A_i は全て異なり、それぞれ1文字以上16文字以下の大文字あるいは小文字アルファベットからなる。軍事的強さ B_i は0以上1000以下の整数で与えられる。隣接している国のリストにある国名 D_i,j は A₁ から A_N のうちいずれかと一致する。また、ある国の隣接国リストにその国自身が含まれることはなく、同じ国名が2回以上重複して含まれることもない。さらに、隣接関係が対称でない場合は入力に存在しない。

入力の終了は0のみからなる行で表される。

各テストケースについて、自国を含めた軍事的強さの和が最大になるような同盟を考えたとき、その強さを求め、1行で出力せよ。

7
INTERCAL 10 3 Chef Piet COW
Chef 7 3 INTERCAL Piet COW
Piet 6 2 INTERCAL Chef
COW 7 2 INTERCAL Chef
J 6 1 A
A 12 1 J
Grass 0 0
7
Qin 105 4 Zhao Wei Han Chu
Zhao 81 4 Qin Wei Qi Yan
Wei 70 5 Qin Zhao Han Qi Chu
Han 45 3 Qin Wei Chu
Qi 79 4 Zhao Wei Chu Yan
Chu 102 4 Qin Wei Han Qi
Yan 53 2 Zhao Qi
14
Magadha 98 8 Macedonia Kalinga Surashtra Ashmaka Kantala Andhra Gangaridai Kamapura
Macedonia 79 2 Magadha Surashtra
Kalinga 51 2 Magadha Andhra
Surashtra 13 3 Magadha Macedonia Ashmaka
Ashmaka 11 3 Magadha Surashtra Kantala
Kantala 12 3 Magadha Ashmaka Andhra
Andhra 14 3 Magadha Kantala Kalinga
Cholas 15 3 Cheras Pandyas Anuradhapuras
Cheras 8 2 Cholas Pandyas
Pandyas 10 3 Cholas Cheras Anuradhapuras
Anuradhapuras 7 2 Cholas Pandyas
Gangaridai 20 3 Magadha Kamapura Arakan
Kamapura 18 2 Magadha Gangaridai
Arakan 7 1 Gangaridai
0

22
184
120