P4437 [HNOI/AHOI2018] Permutation

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.

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 a single integer representing the answer.

### 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