디스크 아레나에서 명성 얻기

그리드 월드의 디스크 아레나는 프로그램들이 다른 프로그램과 원반 검투 경기를 벌이는 장소이다. 아레나에는 $k$개의 경기가 있다. 각 경기에서 승리하면 명성을 얻어 그리드 월드에서 유명해진다. 물론 경기에서 지면 삭제된다. $i$번째 경기에서 승리해 얻는 명성은 $f_i$이며, 이 값은 양수가 아닐 수도 있다.

또한 $i$번째 경기에 출전하려면, 먼저 미리 정해진 경기 집합 $S_i$에 속한 경기들을 모두 치러 이겨 두어야 한다. $S_i$에 속한 경기들을 $i$번째 경기의 선행 경기(prerequisite)라고 부른다. 선행 관계에는 순환이 없다. 예를 들어 경기 $a$가 경기 $b$의 선행 경기이고 $b$가 $c$의 선행 경기이면서 동시에 $c$가 $a$의 선행 경기가 되는 일은 생기지 않는다. 명성이 음수인 경기를 치르는 유일한 이유는, 그 경기가 더 큰 양의 명성을 주는 경기의 선행 경기이기 때문이다.

경기 집합 $C$가 실현 가능(feasible)하다는 것은, $C$에 속한 모든 경기 $i$에 대해 그 선행 경기 $S_i$도 모두 $C$에 포함된다는 뜻이다. 즉 $i \in C$이면 $S_i \subseteq C$이다. 집합 $C$의 명성은 $C$에 속한 모든 경기의 명성의 합이다.

목표는 최대한 유명해지는 것이다. 각 경기의 명성과 선행 관계가 주어질 때, 명성의 합이 최대가 되는 실현 가능한 경기 집합을 찾아라.

아래 그림은 예시이며, 경기 사이의 화살표는 선행 관계를 나타낸다. 첫 번째 예시에서 경기 1은 경기 2와 3을 선행 경기로 가지고, 경기 3은 경기 2를 선행 경기로 가진다. 이때 최대 명성은 집합 ${1, 2, 3}$을 선택했을 때 얻어진다. 경기 3은 명성이 음수이지만 경기 1의 선행 경기이므로 반드시 선택해야 한다. 한편 아무 경기도 선택하지 않는 것(빈 집합, 명성 $0$)도 언제나 실현 가능하므로 답은 결코 음수가 되지 않는다.

입력의 첫 줄에는 테스트 케이스의 개수가 주어진다(최대 $100$).

각 테스트 케이스의 첫 줄에는 경기의 수 $k$가 주어진다($k \le 1000$). 경기에는 $1$부터 $k$까지 번호가 매겨져 있다. 이어지는 $k$개의 줄에 각 경기의 정보가 주어진다. $(i+1)$번째 줄은 다음 형식이다.

$$f_i \quad d_i \quad u_1 \quad u_2 \quad \cdots \quad u_{d_i}$$

첫 번째 수 $f_i$는 경기 $i$에서 승리해 얻는 명성이고, 두 번째 수 $d_i = |S_i|$는 선행 경기의 개수이며, 나머지 $d_i$개의 수 $u_1, \dots, u_{d_i}$는 $S_i$의 원소(선행 경기의 번호)이다.

각 테스트 케이스에서 모든 경기의 선행 경기 개수의 합 $\sum_i |S_i|$은 $6000$ 이하이다.

각 테스트 케이스마다, 실현 가능한 경기 집합으로 얻을 수 있는 최대 명성을 한 줄에 출력한다. $x$번째 테스트 케이스에 대해서는 정확히 다음 형식으로 출력한다.

Case x: Maximum attainable fame = y

여기서 $y$는 최대 명성이다.