시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 256 MB174887150.714%

문제

A company of $n$ employees is due for a restructuring. In the resulting hierarchy, represented as a rooted tree, every node will be the boss of its children.

Each employee has a list of bosses they will accept. In addition, all employees must be assigned a salary. The salary must be a positive integer, and the salary of each boss must be larger than the sum of salaries of their immediate subordinates.

Your task is to structure the company so that all above conditions hold, and the sum of all the salaries is as small as possible.

입력

The first input line contains an integer $n$: the number of employees. The employees are numbered $1$, $2$, $\dots$, $n$.

After this, the input contains $n$ lines that describe the preferences of the employees. The $i$th such line contains an integer $k_i$, followed by a list of $k_i$ integers. The list consists of all employees that the $i$th employee accepts as their boss.

출력

You should output the lowest total salary among all valid restructurings. You can assume that at least one solution exists.

서브태스크 1 (22점)

  • $2 \le n \le 10$
  • $\sum_{i=1}^{n}{k_i} \le 20$

서브태스크 2 (45점)

  • $2 \le n \le 100$
  • $\sum_{i=1}^{n}{k_i} \le 200$

서브태스크 3 (33점)

  • $2 \le n \le 5000$
  • $\sum_{i=1}^{n}{k_i} \le 10000$

예제 입력 1

4
1 4
3 1 3 4
2 1 2
1 3

예제 출력 1

8

채점 및 기타 정보

  • 예제는 채점하지 않는다.