스팸웨이 대파업

스팸웨이(Spamway)는 좀비 컴퓨터로 이루어진 피라미드 조직을 이용해 상품 주문을 받고 처리하는 메시징 서비스이다. 그런데 모든 좀비가 더 좋은 RAM을 요구하며 파업에 들어갔다. 스팸웨이는 파업 기간에도 영업을 이어 가려고 대체 좀비들을 새로 고용했지만, 이 대체 좀비들은 조직력이 형편없어서 네트워크를 잘 구성하지 못한다.

당신의 임무는 대체 좀비들을 잘 조직하여, 스팸웨이가 한 번의 주문 라운드를 처리하는 데 걸리는 시간을 최소로 만드는 것이다. 구체적으로, 다음 두 조건을 만족하도록 각 좀비에게 부하 목록을 배정해야 한다.

1. 우두머리 좀비를 제외한 모든 좀비는 정확히 한 명의 상급자를 가진다.
2. 모든 좀비는 결국 우두머리 좀비에게 보고하게 된다.

한 번의 주문 라운드는 다음과 같이 진행된다. 우두머리 좀비는 자신의 모든 부하에게 동시에 "구매 주문 목록을 보내라"는 요청 메시지를 보낸다. 이런 요청을 받은 좀비는 자신의 모든 부하에게 똑같은 요청을 보낸다. 모든 부하로부터 답장을 받은 좀비는, 받은 목록들과 자신이 받은 구매 주문 목록을 하나로 합쳐서 자신의 상급자에게 보낸다.

좀비를 조직하기 위해 알아야 할 규칙은 다음과 같다.

1. 한 좀비는 여러 개의 메시지를 동시에 보낼 수 있다.
2. 모든 메시지는 목적지에 도착하는 데 $10$초가 걸린다(모든 데이터는 고도로 압축되어 이 놀라운 효율을 낸다).
3. 파업하지 않은 관리자가 한 명 있어 우두머리 좀비 역할을 한다. 이 관리자가 바로 지연 시간이 없는 우두머리 좀비 $Z_0$이다.
4. 모든 좀비는 셀룰러 모뎀으로 통신한다. 다만 신호가 약한 탓에 모든 좀비가 서로 통신할 수 있는 것은 아니다.
5. 스팸웨이는 매우 검소해서, 관리자(우두머리 좀비 역할)를 포함하여 좀비를 최대 $100$마리까지만 사용한다.
6. 각 대체 좀비에게는 $Z_0, Z_1, Z_2, Z_3, \dots$ 과 같은 비밀 코드명이 붙는다. $Z_0$이 우두머리 좀비이다.
7. 대체 좀비는 훈련이 부족해서, 받은 메시지를 다 "읽는" 데 일정 시간이 걸린다. 이 지연 시간(좀비 대기 시간)은 좀비마다 다르며, $1000$초 미만의 음이 아닌 정수 초이다. 좀비는 여러 메시지를 동시에 읽을 수 있지만, 다 읽기 전에는 그 메시지에 따라 행동할 수 없다. 우두머리 좀비 $Z_0$은 지연 시간이 없다.

또한 상급자-부하 관계가 성립하려면 두 좀비가 서로 안정적으로 연락할 수 있어야 한다. 상급자는 부하에게 요청을 보내야 하고, 부하는 상급자에게 답장을 보내야 하기 때문이다.

첫 번째 줄에 새로 고용된 대체 좀비의 수 $n$이 주어진다 ($1 \le n \le 99$). 관리자(우두머리 좀비)는 이 수에 포함되지 않는다.

이어서 $n + 1$개의 줄이 주어진다. 각 줄에는 한 좀비의 좀비 대기 시간, 그 좀비가 안정적으로 연락할 수 있는 좀비의 수, 그리고 그 좀비들의 번호 목록이 순서대로 주어진다. 첫 번째 줄은 우두머리 좀비 $Z_0$을 설명하고, 이후 $n$개의 줄은 순서대로 $Z_1$부터 $Z_n$까지를 설명한다. 각 번호는 $0$부터 $n$ 사이의 정수로, 해당 좀비의 코드명에 붙은 숫자이다.

한 번의 주문 라운드에서 데이터를 보내고 받는 데 필요한 총 시간을 하나의 정수로 출력한다. 여러 가지 조직 방법이 있을 수 있는데, 그중 최적인 방법에 대한 시간을 구해서 출력해야 한다.

아래 예제를 살펴보자. 이 예제에서 가능한 조직은 하나뿐이다. $Z_0$의 부하는 $Z_1$과 $Z_3$이고, $Z_1$과 $Z_2$에게는 부하가 없으며, $Z_3$의 유일한 부하는 $Z_2$이다.

$Z_0$이 주문 라운드를 시작하는 시각을 $0$이라 하자. $Z_0$은 $Z_1$과 $Z_3$에게 요청을 보낸다. 시각 $10$에 $Z_1$과 $Z_3$이 메시지를 받는다. $Z_3$은 메시지를 읽는 데 $3$초가 걸려 시각 $13$에 다 읽고, 부하인 $Z_2$에게 요청을 보낸다. 시각 $23$에 $Z_2$가 $Z_3$의 메시지를 받고 $7$초 동안 읽어 시각 $30$에 마친다. $Z_2$에게는 부하가 없으므로 곧바로 자신의 주문 목록을 상급자 $Z_3$에게 보낸다. 시각 $40$에 $Z_3$이 그 목록을 받고 $3$초 동안 읽어 시각 $43$에 마친 뒤, $Z_2$의 목록과 자신의 목록을 합쳐 $Z_0$에게 보내고, 시각 $53$에 도착한다. 한편 $Z_1$은 시각 $10$에 받은 $Z_0$의 메시지를 $50$초 동안 읽어 시각 $60$에 마치고, 곧바로 자신의 주문 목록을 $Z_0$에게 보내 시각 $70$에 도착한다. 이 메시지를 받은 순간 $Z_0$은 스팸웨이로 들어온 모든 구매 주문을 갖게 되며, 주문 라운드가 끝난다. 따라서 총 시간은 $70$이다.