H. Cinematic Hierarchy
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

BRUTE, a group originally known for their performance in competitive programming contests, decided to change direction and venture into the world of cinema. Risa, a renowned director from the group, was tasked with selecting some actors from $$$N$$$ candidates for the first film produced by BRUTE.

To do this, Risa contacted all the actors and collected their conditions for participating in the project. Each actor, in addition to demanding a monetary value, indicated names of other more famous actors they would like to work with, requiring that these also be included in the cast. Each actor is identified by a number, where the $$$i$$$-th least famous actor is represented by the number $$$i$$$, meaning that the most famous actor is represented by the number $$$N$$$, the next most famous by $$$N - 1$$$, and so on.

After organizing all the requirements, Risa noticed two things:

  • Each actor appears in at most one other actor's requirement.
  • There is exactly one actor who is not required by any other, and this actor is the least famous among all.

Knowing that the $$$i$$$-th actor generates a profit of $$$a_i$$$ if hired (negative values represent a loss), what is the maximum possible profit that BRUTE can obtain if Risa optimally chooses which actors to hire? Note that Risa may choose to hire no actors at all.

Input

The first line of the input contains an integer $$$N$$$ $$$(2 \le N \le 5 \cdot 10^5)$$$, representing the number of candidates Risa has available.

The second line contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ $$$(-10^9 \le a_i \le 10^9)$$$, where $$$a_i$$$ represents the profit the $$$i$$$-th actor will generate if hired for the film.

The third and last line contains $$$N - 1$$$ integers $$$s_2, s_3, \dots, s_N$$$ $$$(1 \le s_i \lt i)$$$, indicating that actor $$$s_i$$$ required the participation of actor $$$i$$$ in the cast.

Output

The output must contain exactly one line, the maximum profit BRUTE can obtain if Risa optimally chooses which actors to hire.

Examples
Input
9
-8 -1 21 -1 -10 -10 9 8 8
1 2 2 3 3 6 4 6
Output
26
Input
4
-10 -8 -9 -10
1 1 2
Output
0
Input
7
1 -5 1 9 2 0 -7
1 2 1 4 4 2
Output
12
Note

In the first case, Risa can hire actors $$$3$$$, $$$5$$$, $$$6$$$, $$$7$$$, $$$8$$$, and $$$9$$$, to obtain a profit of $$$21 - 10 -10 + 9 + 8 + 8 = 26$$$.

Above is an illustration of the first case; the numbers inside the nodes represent the actors, while the dotted circle above them shows their generated profit $$$a_i$$$. Each directed edge from $$$i$$$ to $$$j$$$ means actor $$$i$$$ required actor $$$j$$$. The nodes highlighted with a surrounding circle represent a possible optimal set of hired actors.