题目描述

有 $n$ 个按时间先后编号的穿梭点，第 $i$ 个点的影响值为 $s_i$，影响值可能为负数。旅行者从第 $1$ 个点出发，最终要到达第 $n$ 个点。

位于第 $i$ 个点时，可以前往第 $i+1$ 个点，也可以通过该点的跳板前往第 $k_i$ 个点。每次到达一个点，都会获得该点的影响值；第 $1$ 个点和第 $n$ 个点的影响值也要计算。

请计算能够获得的最大影响值总和。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $s_1,s_2,\ldots,s_n$。

第三行包含 $n-1$ 个整数 $k_1,k_2,\ldots,k_{n-1}$，表示每个跳板的终点。

输出格式

输出一个整数，表示最大影响值总和。

3
4 -2 6
3 3

10

数据范围与提示

• $2 \le n \le 100000$
• $-10^7 \le s_i \le 10^7$
• $i<k_i \le n$