题目内容

有一个比较复杂的软件系统需要部署到客户提供的服务器上。该软件系统的安装过程可以分成若干个小步骤，某些步骤间存在依赖关系，被依赖的步骤必须先执行完，才能执行后续的安装步骤。满足依赖条件的多个步骤可以并行执行。请你开发一个调度程序，以最短的时间完成软件的部署。

输入描述

• 第一行：整数 N（0 < N ≤ 10000），总步骤数。
• 第二行：N 个以空格分隔的整数，代表每个步骤所需的时间。该行所有整数之和不大于 int32。
• 第三行开始的 N 行：表示每个步骤所依赖的其它步骤的编号（编号从 1 开始，行号减 2 表示步骤的编号）。如果依赖多个步骤，用空格分隔；-1 表示无依赖。
• 测试用例确保各个安装步骤不会出现循环依赖。

输出描述

一个整数，代表最短执行时间。

样例1

输入

4
6 2 1 2
-1
-1
1
3

输出

9

说明
共4个步骤

每个步骤所需的时间分别为6 2 1 2

步骤1和步骤2无依赖，可并发执行;步骤3依赖步骤1;步骤4依赖步骤

总的最小执行时间为6+1+2=9

样例2

输入

4
1 2 3 4
2 3
3
-1
1

输出

10

说明

步骤 1 依赖步骤 2 和步骤 3；

步骤 2 依赖步骤 3；

步骤 3 无依赖；

步骤 4 依赖步骤 1。

执行顺序为：

步骤 3 → 步骤 2 → 步骤 1 → 步骤 4；

总的最小执行时间为 3 + 2 + 1 + 4 = 10