题目描述

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

• 她可以直接走到下一个位置（也就是 $i+1$ 号位置）；
• 也可以选择跳到第 $t_i$ 号位置（保证$i<t_i$）。

小爱的得分就是一路上经过的所有位置的分数之和，请问应该如何安排行动，才能使获得的分数之和达到最大？

输入格式

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

输出格式

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

3
4 -2 6
3 3

10

数据范围

• 对于 $30\%$ 的数据，保证 $1\leq n\leq 50$；
• 对于 $60\%$ 的数据，保证 $1\leq n\leq 5000$；
• 对于 $100\%$ 的数据，保证 $1\leq n\leq 100,000$；
• $-10^7 \leq a_i \leq 10^7$；
• $i \lt t_i \leq n$；