G. Gelatos from Goiás
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Lucas is the owner of a new franchise of Heladitos from Goiás, specialized in producing gelatos with typical fruits from the Cerrado. Soon, a national competition will take place to elect the best gelato in Brazil, and Lucas intends to participate by launching a striking flavor: Pequi Gelato.

To evaluate the quality of a gelato, Lucas uses a formula defined as the product of the smallest score of the chosen subset of ingredients and the size of that subset. Formally, let $$$I$$$ be the set of available ingredients and $$$E$$$ the subset of ingredients chosen for gelato $$$g$$$ ($$$E \subseteq I$$$), its quality $$$Q_g$$$ is given by:

$$$Q_g = \min_{x \in E} \, (x) \; \cdot \; |E|$$$

Lucas organized a list $$$a$$$ with $$$N$$$ values, corresponding to the score of each available ingredient. Additionally, to prevent the odor of the gelato from becoming unbearable, he defined a derangement $$$P$$$, where the $$$i$$$-th ingredient cannot be used together with the $$$P_i$$$-th ingredient.

Due to high demand in his store, Lucas does not have time to make this choice himself. Thus, he asks for your help to determine, based on the list of ingredients and the permutation $$$P$$$, what is the highest possible quality value that can be obtained.

Input

The first line contains an integer $$$N$$$ $$$(2 \leq N \leq 10^5)$$$, representing the number of available ingredients.

The second line contains $$$N$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$, where each $$$a_i$$$ indicates the score of the $$$i$$$-th available ingredient.

The third line contains $$$N$$$ integers $$$P_i$$$ $$$(1 \leq P_i \leq N)$$$, which define the derangement $$$P$$$. It is guaranteed that $$$P_i \neq i$$$ for all $$$i$$$, and that for any $$$i \neq j$$$, $$$P_i \neq P_j$$$.

Output

Print a single line containing an integer $$$Q$$$, representing the highest possible quality value that can be obtained from the choice of ingredients, following the restrictions defined by the derangement $$$P$$$.

Examples
Input
5
10 5 6 7 8
2 3 4 5 1
Output
14
Input
4
2 3 4 5
3 4 2 1
Output
8
Input
5
1 4 5 6 7
5 3 2 1 4
Output
10