The Enemy of My Enemy is My Friend

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

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

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

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

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

N
A1 B1 C1 D1,1... D1,C1
A2 B2 C2 D2,1... D2,C2
...
AN BN CN DN,1... DN,CN

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

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

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

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