题目描述

假设你是电子科技大学的学生李华，在 4202 年的某一期一站到底中，你作为选手参加了节目的录制。不同于 2000 多年前的规则，节目中不会进行选手两两对战并抢答或轮答题目的环节，每位选手的答题以单人赛的方式进行，具体规则如下：

在选手的答题环节开始前，系统会从题库中抽取 $n$ 道题，每道题根据难度系数有 $a_i$ 的分值。主持人会在一开始公布所有的题目内容和分值，之后进入选手的答题环节。

为了增加节目的趣味性，在答题环节中，选手并不能随意选择作答题目的顺序。具体的，除 $1$ 号题目外所有题目有且仅有一道前置题目，在选手正确作答出某道题的前置题目后才可以进行作答这道题。节目组保证编号为 $i$ 的题目的前置题目编号必然小于 $i$。

此外，如果选手作答题目时提交了错误答案，那么其脚下的地板将立刻打开，选手掉落并结束作答，此前答对的所有题目的分值之和就是该选手的得分。如果选手答对了所有的题目，那么所有题目的分值之和就是该选手的得分。

现在你已经看完了所有的题目，根据你的知识储备，你判断出了每道题你做对的概率 $p_i$。你需要在最短时间内制定出最优的做题策略去最大化你的期望得分，请输出这个得分，并以参加这次节目的过程为主题写一篇不少于 120 词的英语作文。

输入格式

第一行一个正整数 $n$ $(2\le n\le 10^5)$，代表题目的数量。

接下来一行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$ $(1\leq a_i\leq 10^6)$，$a_i$ 代表编号为 $i$ 的题目的分值。

接下来一行 $n$ 个实数 $p_1,p_2,\ldots,p_n$ $(0<p_i<1)$，$p_i$ 代表你答对编号为 $i$ 的题目的概率。

接下来一行 $n-1$ 个正整数 $t_1,t_2,\ldots,t_{n-1}$ $(1\leq t_i\leq i)$，$t_i$ 代表编号为 $i+1$ 的题目的前置题目的编号。

输出格式

输出一行一个实数，代表在最优做题策略下的期望得分。

假设你的输出是 $a$，答案是 $b$，当且仅当 $\frac{|a-b|}{\max(1,b)}\le 10^{-9}$ 时，你的答案会被认为是正确的。

5
5 4 3 2 1
0.9 0.89 0.88 0.87 0.86
1 1 2 2

11.572522416

提示

在样例中，分值越高的题目你也有越大的概率答对，显然按照 $1,2,3,4,5$ 的顺序去答题最优。