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 called a valid permutation if and only if it satisfies: for any $k$ and any $j$, if $j \le k$, then $a_{p[j]} \neq p[k]$. (In other words: for any $k$ and any $j$, if $p[k] = 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.

The sample explanation provides examples of valid and invalid permutations.

Input

The first line contains an integer $n$. The next line contains $n$ integers, representing $a_1, a_2, \dots, a_n$. The next line contains $n$ integers, representing $w_1, w_2, \dots, w_n$.

Output

Output a single integer representing the answer.

Examples

Input 1

3
0 1 1
5 7 3

Output 1

32

Note 1

For $a_1=0, a_2=1, a_3=1$, the permutations are: $a_1=0, a_2=1, a_3=1$, is a valid permutation, the weight is $1 \times 5 + 2 \times 7 + 3 \times 3 = 28$; $a_2=1, a_1=0, a_3=1$, is an invalid permutation, because $a_{p[1]} = p[2]$; $a_1=0, a_3=1, a_2=1$, is a valid permutation, the weight is $1 \times 5 + 2 \times 3 + 3 \times 7 = 32$; $a_3=1, a_1=0, a_2=1$, is an invalid permutation, because $a_{p[1]} = p[2]$; $a_2=1, a_3=1, a_1=0$, is an invalid permutation, because $a_{p[1]} = p[3]$; $a_3=1, a_2=1, a_1=0$, is an invalid permutation, because $a_{p[1]} = p[3]$. Therefore, the maximum weight is 32.

Input 2

3
2 3 1
1 2 3

Output 2

-1

Note 2

For $a_1=2, a_2=3, a_3=1$, the permutations are: $a_1=2, a_2=3, a_3=1$, is an invalid permutation, because $a_{p[1]} = p[2]$; $a_2=3, a_1=2, a_3=1$, is an invalid permutation, because $a_{p[1]} = p[3]$; $a_1=2, a_3=1, a_2=3$, is an invalid permutation, because $a_{p[1]} = p[3]$; $a_3=1, a_1=2, a_2=3$, is an invalid permutation, because $a_{p[2]} = p[3]$; $a_2=3, a_3=1, a_1=2$, is an invalid permutation, because $a_{p[2]} = p[3]$; $a_3=1, a_2=3, a_1=2$, is an invalid permutation, because $a_{p[1]} = p[3]$. Therefore, there is no valid permutation.

Input 3

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

Output 3

809

Constraints

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 100000$. For 100% of the data, $1 \le n \le 500000$, $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}$.