Problem Description

Given \( n \) integers \( a_1, a_2, \dots, a_n \) where \( 0 \le a_i \le n \), and \( n \) integers \( w_1, w_2, \dots, w_n \). A permutation \( a_{p[1]}, a_{p[2]}, \dots, a_{p[n]} \) of \( a_1, a_2, \dots, a_n \) is considered valid if and only if for any \( k \) and any \( j \), if \( j \le k \), then \( a_{p[j]} \) is not equal to \( p[k] \). (In other words, for any \( k \) and any \( j \), if \( p[k] \) equals \( a_{p[j]} \), then \( k < j \).) The weight of this valid permutation is defined as \( w_{p[1]} + 2w_{p[2]} + \dots + nw_{p[n]} \).

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

Examples are provided to illustrate valid and invalid permutations.

Input Format

The first line contains an integer \( n \).

The next line contains \( n \) integers, representing \( a_1, a_2, \dots, a_n \).

The following line contains \( n \) integers, representing \( w_1, w_2, \dots, w_n \).

Output Format

Output a single integer representing the answer.

Sample Input and Output

Input Sample #1

3
0 1 1
5 7 3

Output Sample #1

32

Input Sample #2

3
2 3 1
1 2 3

Output Sample #2

-1

Input Sample #3

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

Output Sample #3

809

Notes

Sample Explanation 1

For \( a_1 = 0, a_2 = 1, a_3 = 1 \), the permutations are:

• \( a_1 = 0, a_2 = 1, a_3 = 1 \), valid, weight is \( 1*5 + 2*7 + 3*3 = 28 \);
• \( a_2 = 1, a_1 = 0, a_3 = 1 \), invalid because \( a_{p[1]} \) equals \( p[2] \);
• \( a_1 = 0, a_3 = 1, a_2 = 1 \), valid, weight is \( 1*5 + 2*3 + 3*7 = 32 \);
• \( a_3 = 1, a_1 = 0, a_2 = 1 \), invalid because \( a_{p[1]} \) equals \( p[2] \);
• \( a_2 = 1, a_3 = 1, a_1 = 0 \), invalid because \( a_{p[1]} \) equals \( p[3] \);
• \( a_3 = 1, a_2 = 1, a_1 = 0 \), invalid because \( a_{p[1]} \) equals \( p[3] \).

Thus, the maximum weight is \( 32 \).

Sample Explanation 2

For \( a_1 = 2, a_2 = 3, a_3 = 1 \), the permutations are:

• \( a_1 = 2, a_2 = 3, a_3 = 1 \), invalid because \( a_{p[1]} \) equals \( p[2] \);
• \( a_2 = 3, a_1 = 2, a_3 = 1 \), invalid because \( a_{p[1]} \) equals \( p[3] \);
• \( a_1 = 2, a_3 = 1, a_2 = 3 \), invalid because \( a_{p[1]} \) equals \( p[3] \);
• \( a_3 = 1, a_1 = 2, a_2 = 3 \), invalid because \( a_{p[2]} \) equals \( p[3] \);
• \( a_2 = 3, a_3 = 1, a_1 = 2 \), invalid because \( a_{p[2]} \) equals \( p[3] \);
• \( a_3 = 1, a_2 = 3, a_1 = 2 \), invalid because \( a_{p[1]} \) equals \( p[3] \).

Thus, there are no valid permutations.

Data Range

For the first 20% of the data, \( 1 \le n \le 10 \).

For the first 40% of the data, \( 1 \le n \le 15 \).

For the first 60% of the data, \( 1 \le n \le 1000 \).

For the first 80% of the data, \( 1 \le n \le 10^5 \).

For 100% of the data, \( 1 \le n \le 5 \times 10^5 \), \( 0 \le a_i \le n \), \( 1 \le w_i \le 10^9 \), the sum of all \( w_i \) does not exceed \( 1.5 \times 10^{13} \).

见题面 Input 部分

见题面 Output 部分