Description

Given $n$ integers $a_1, a_2, \dots, a_n, 0 \le a_i \le n$, and $n$ integers $w_1, w_2, \dots, w_n$. Call a permutation $a_{p_1}, a_{p_2}, \dots, a_{p_n}$ of $a_1, a_2, \dots, a_n$ a valid permutation of $a_1, a_2, \dots, a_n$ if and only if it satisfies: for any $k$ and any $j$, if $j \le k$, then $a_{p_j} \ne p_k$. (In other words: for any $k$ and any $j$, if $p_k = a_{p_j}$, then $k < j$.) Define the weight of this valid permutation as $w_{p_1} + 2 w_{p_2} + \dots + n w_{p_n}$.

You need to find the maximum weight among all valid permutations. If no valid permutation exists, output $-1$.

The sample explanations include examples of valid and invalid permutations.

Input Format

The first line contains an integer $n$.

The next line contains $n$ integers, denoting $a_1, a_2, \dots, a_n$. The following line contains $n$ integers, denoting $w_1, w_2, \dots, w_n$.

Output Format

Output a single integer representing the answer.

3 
0 1 1 
5 7 3 

32

3 
2 3 1 
1 2 3 

-1

10 
6 6 10 1 7 0 0 1 7 7 
16 3 10 20 5 14 17 17 16 13 

809

Hint

Sample Explanation 1

For $a_1 = 0, a_2 = 1, a_3 = 1$, its permutations are:

• $a_1 = 0, a_2 = 1, a_3 = 1$, this is a valid permutation, and its weight is $1\times 5 + 2\times 7 + 3\times 3 = 28$;
• $a_2 = 1, a_1 = 0, a_3 = 1$, this is an invalid permutation because $a_{p_2}$ equals $p_2$;
• $a_1 = 0, a_3 = 1, a_2 = 1$, this is a valid permutation, and its weight is $1\times 5 + 2\times 3 + 3\times 7 = 32$;
• $a_3 = 1, a_1 = 0, a_2 = 1$, this is an invalid permutation because $a_{p_1}$ equals $p_2$;
• $a_2 = 1, a_3 = 1, a_1 = 0$, this is an invalid permutation because $a_{p_1}$ equals $p_3$;
• $a_3 = 1, a_2 = 1, a_1 = 0$, this is an invalid permutation because $a_{p_1}$ equals $p_3$.

Therefore, the maximum weight is $32$.

Sample Explanation 2

For $a_1 = 2, a_2 = 3, a_3 = 1$, its permutations are:

• $a_1 = 2, a_2 = 3, a_3 = 1$, this is an invalid permutation because $a_{p_1}$ equals $p_2$;
• $a_2 = 3, a_1 = 2, a_3 = 1$, this is an invalid permutation because $a_{p_1}$ equals $p_3$;
• $a_1 = 2, a_3 = 1, a_2 = 3$, this is an invalid permutation because $a_{p_1}$ equals $p_3$;
• $a_3 = 1, a_1 = 2, a_2 = 3$, this is an invalid permutation because $a_{p_2}$ equals $p_3$;
• $a_2 = 3, a_3 = 1, a_1 = 2$, this is an invalid permutation because $a_{p_2}$ equals $p_3$;
• $a_3 = 1, a_2 = 3, a_1 = 2$, this is an invalid permutation because $a_{p_1}$ equals $p_3$.

Therefore, there is no valid permutation.

Constraints

• For the first $20\%$ of the testdata, $1 \le n \le 10$.
• For the first $40\%$ of the testdata, $1 \le n \le 15$.
• For the first $60\%$ of the testdata, $1 \le n \le 1000$.
• For the first $80\%$ of the testdata, $1 \le n \le 10^5$.
• For $100\%$ of the testdata, $1 \le n \le 5\times 10^5$, $0 \le a_i \le n$, $1 \le w_i \le 10^9$, and the sum of all $w_i$ does not exceed $1.5\times 10^{13}$.

Translated by ChatGPT 5