一家拥有 $n$ 名员工的公司即将进行重组。在重组后的层级结构中（表示为一棵有根树），每个节点都是其子节点的上司。

每位员工都有一个他们可以接受的上司列表。此外，必须为所有员工分配薪水。薪水必须是正整数，且每位上司的薪水必须大于其所有直接下属的薪水之和。

你的任务是构建公司的层级结构，使得上述所有条件均成立，且所有员工的薪水总和尽可能小。

输入格式

第一行包含一个整数 $n$：员工数量。员工编号为 $1, 2, \dots, n$。

接下来包含 $n$ 行，描述员工的偏好。第 $i$ 行包含一个整数 $k_i$，后跟 $k_i$ 个整数。该列表包含了第 $i$ 位员工可以接受的所有上司。

输出格式

输出所有合法重组方案中最低的薪水总和。你可以假设至少存在一个可行解。

样例

输入格式 1

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

输出格式 1

8

子任务

• 子任务 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$