题目描述

Daddy Duck 是一名文件管理大师，他在自己的计算机上用一组结构清晰合理的文件夹储存自己的文件，例如：

daddyduck/
  folder1/
    file1
    folder2/
      file2
  folder3/
    file3
  file4

Daddy Duck 的文件管理中，只有一个“顶层”的文件夹（这里是 daddyduck）。

作为一个优秀的命令行大师，Daddy Duck 一般通过相对路径访问自己的文件。在相对路径中用 .. 表示上级目录。例如假设 Daddy Duck 此刻位于目录 folder2 下，他可以用如下相对路径访问四个文件：

../file1
file2
../../folder3/file3
../../file4

现在，Daddy Duck 想要找到一个目录，使得位于该目录访问所有文件的相对路径的长度之和最小。

输入

第一行包含一个整数 $N(1\le N\le 10^5)$，表示所有文件和文件夹的数量。为了便于输入，每个对象（文件/文件夹）被赋予一个唯一的 $ID(\in[1,N])$，其中 $ID=1$ 的为顶层文件夹。

接下来 $N$ 行，第 $i$ 行描述 $ID=i$ 的对象。每行的第一项为一个长度不超过 $16$，仅包含小写字母和数字的字符串，表示对象的名称；第二项为一个整数 $m$：若 $m=0$ 表示该对象为一个文件；若 $m>0$ 表示该对象为一个包含 $m$ 个对象的文件夹，并在之后输入 $m$ 个整数，表示包含的对象的 $ID$。

输出

输出所有文件的相对路径的长度之和的最小值。注意这个值可能超过 32 位整数的表示范围。

样例

8
daddyduck 3 2 6 8
folder1 2 3 4
file1 0
folder2 1 5
file2 0
folder3 1 7
file3 0
file4 0

42

样例解释

Daddy Duck 在 folder1 访问四个文件的相对路径为：

file1
folder2/file2
../folder3/file3
../file4

此时长度之和最小，为 $42$。