F. One Stop to the End
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Assume you are a student named Li Hua at UESTC. In a certain episode of "One Stop to the End" in the year 4202, you participated as a contestant in the program's recording. Unlike the rules from over 2000 years ago, the program does not involve contestants competing in pairs and answering questions in a round-robin format. Instead, each contestant answers questions individually, with the following specific rules:

Before the contestant's answering phase begins, the system will randomly select $$$n$$$ questions from the question bank, each with a score of $$$a_i$$$ based on its difficulty level. The host will announce all the questions and their scores at the beginning, and then the contestant's answering phase will commence.

To make the program more interesting, contestants cannot freely choose the order in which they answer the questions. Specifically, except for the first question, each question has one and only one prerequisite question. A contestant can only answer a question after correctly answering its prerequisite question. The program ensures that the prerequisite question number for question $$$i$$$ is always less than $$$i$$$.

Furthermore, if a contestant submits an incorrect answer to a question, the floor beneath him/her will immediately open, causing the contestant to fall and end their answering. The sum of the scores of all the questions answered correctly before this point will be the contestant's final score. If a contestant answers all the questions correctly, the sum of the scores of all the questions will be the contestant's final score.

Now that you have read all the questions, based on your knowledge, you have determined the probability $$$p_i$$$ of answering each question correctly. You need to devise the optimal answering strategy to maximize your expected score in the shortest time possible. Please output this score.

Input

The first line contains a positive integer $$$n$$$ ($$$2\le n\le 10^5$$$), representing the number of questions.

The next line contains $$$n$$$ positive integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq 10^6$$$), where $$$a_i$$$ represents the score of question $$$i$$$.

The following line contains $$$n$$$ real numbers $$$p_1,p_2,\ldots,p_n$$$ ($$$0 \lt p_i \lt 1$$$), where $$$p_i$$$ represents the probability of answering question $$$i$$$ correctly.

The next line contains $$$n-1$$$ positive integers $$$t_1,t_2,\ldots,t_{n-1}$$$ ($$$1\leq t_i\leq i$$$), where $$$t_i$$$ represents the number of the prerequisite question for question $$$i+1$$$.

Output

Output a single real number, representing the expected score under the optimal answering strategy.

If your output is $$$a$$$ and the correct answer is $$$b$$$, your answer will be considered correct if and only if $$$\frac{|a-b|}{\max(1,b)}\le 10^{-9}$$$.

Example
Input
5
5 4 3 2 1
0.9 0.89 0.88 0.87 0.86
1 1 2 2
Output
11.572522416
Note

In the sample case, it is obvious that answering the questions in the order of $$$1,2,3,4,5$$$ will yield the optimal result, as the higher-scoring questions also have a higher probability of being answered correctly.