问题文

dwango员工的尼万君是一名从事应用程序开发的工程师。尼万君每天都要进行应用程序的构建、测试和部署等工作。为了提高工作效率，尼万君决定编写一个能够适当执行这些具有依赖关系的任务的程序。

共有N个任务，执行第i个任务会将结果写入磁盘的数据量为xi MB。然而，任务可能依赖于其他任务，只有在所有依赖的任务执行结果都写入磁盘后，该任务才能执行。第i个（2≤i≤N）任务所依赖的任务是ai。

已知N个任务间的依赖关系构成一个连通的有向树。换句话说，对于任何任务来说，它作为依赖任务的任务只有一个。但是，第一个任务是一个例外，没有任何任务依赖它。第一个任务直接或间接地依赖于其他所有任务。

尼万君的目标是执行第一个任务并将结果写入磁盘。此外，尼万君希望尽可能节省计算资源。尼万君可以在执行任意任务后选择删除磁盘上正在写入的任意数量的任务结果。此外，为了节省时间计算量，尼万君确保不会多次执行同一个任务。

为了获得第一个任务的执行结果，尼万君需要多少磁盘空间？请按适当的顺序执行任务和删除执行结果，使得过程中的最大磁盘使用量（执行结果的总量）最小。请输出这个最小值（以MB为单位）。

约束条件

• 1≤N≤20
• 1≤xi≤1,000,000（1≤i≤N）
• 1≤ai≤i−1（2≤i≤N）

输入

输入以以下格式从标准输入中给出。

N x1 x2 x3 ... xN a2 a3 ... aN

输出

输出答案。

示例1

5
3 5 2 4 6
1 1 2 2```

#### 输出示例1

```plain
15```

操作

磁盘消耗

执行任务4

4 (= 4)

执行任务5

10 (= 4 + 6)

执行任务2

15 (= 4 + 6 + 5)

删除任务4、5的结果

5 (= 5)

执行任务3

7 (= 5 + 2)

执行任务1

10 (= 5 + 2 + 3)

通过以上操作，最大磁盘消耗量为15 MB。这是最优解。

#### 示例2

```plain
2
3 5
1```

#### 输出示例2

```plain
8```

#### 示例3

```plain
5
1 2 3 4 5
1 2 3 4```

#### 输出示例3

```plain
9```