该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 $n$ 个位置排成一排，第 $i$ 个位置都有一个分数 $a_i$ （分数可能是正数，也可能是负数）。小明从 $1$ 号位置出发，最终要走到 $n$ 号位置。当小爱在第 $i$ 个位置时，有两种选择：

他可以直接走到下一个位置（也就是 $i+1$ 号位置）；

也可以选择跳到第 $t_i$ 号位置（保证$i<t_i$）。 小明的得分就是一路上经过的所有位置的分数之和，请问应该如何安排行动，才能使获得的分数之和达到最大？

输入格式

第一行：一个整数 $n$； 第二行：$n$ 个整数，表示 $a_1,a_2,⋯,a_n$； 第三行：$n−1$个整数，表示 $t_1,t_2,⋯,t_{n−1}$；

输出格式

单个整数：表示可能拿到的最高分数。

3
4 -2 6
3 3

10

5
0 -2 3 0 0
4 5 5 5

1

数据规模与约定

对于 $30$% 的数据，保证 $1≤n≤50$；

对于 $60$% 的数据，保证 $1≤n≤5000$；

对于 $100$% 的数据，保证 $1≤n≤100,000$；

$−10^7≤a_i≤10^7；i<t_i≤n$；