적의 적은 나의 친구
시간 제한8초메모리 제한512 MB
나라들의 인접 그래프가 주어질 때, 우리나라를 포함하고 선택된 두 나라가 서로 이웃이거나 같은 이웃을 가지지 않도록 하면서 군사력 합을 최대로 하는 동맹을 고른다.
문제
때는 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가 주어진다. 자기 나라는 첫 번째 나라 A1이다.
나라 이름 Ai는 모두 다르며, 각각 1자 이상 16자 이하의 대문자 또는 소문자 알파벳으로 이루어진다. 군사적 강함 Bi는 0 이상 1000 이하의 정수로 주어진다. 인접한 나라의 목록에 있는 나라 이름 Di,j는 A1부터 AN 중 하나와 일치한다. 또한 어떤 나라의 인접국 목록에 그 나라 자신이 포함되지 않으며, 같은 나라 이름이 두 번 이상 중복해서 포함되지도 않는다. 인접 관계가 대칭이 아닌 경우는 입력에 존재하지 않는다.
입력의 끝은 0만으로 이루어진 행으로 나타낸다.
출력
각 테스트 케이스마다 자기 나라를 포함한 군사적 강함의 합이 최대가 되도록 동맹을 맺었을 때, 그 강함의 합을 한 줄에 출력한다.