English text is not available in this practice contest.
時は 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行で出力せよ。
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