[HNOI/AHOI2018] 排列

给定 $n$ 个整数 $a_1, a_2, \dots, a_n, 0 \le a_i \le n$，以及 $n$ 个整数 $w_1, w_2, \dots, w_n$。称 $a_1, a_2, \dots, a_n$的 一个排列 $a_{p[1]}, a_{p[2]}, \dots, a_{p[n]}$为 $a_1, a_2, \dots, a_n$的一个合法排列，当且仅当该排列满足：对于任意 的 $k$ 和任意的 $j$，如果 $j \le k$，那么 $a_{p[j]}$不等于 $p[k]$。（换句话说就是：对于任意的 $k$ 和任意的 $j$，如果 $p[k]$等于 $a_{p[j]}$，那么 $k<j$。）定义这个合法排列的权值为 $w_{p[1]} + 2w_{p[2]} + \dots + nw_{p[n]}$。 你 需要求出在所有合法排列中的最大权值。如果不存在合法排列，输出 $-1$ 。 样例解释中给出了合法排列和非法排列的实例。

第一行一个整数 $n$。 接下来一行 $n$ 个整数，表示$a_1, a_2, \dots, a_n$ 。 接下来一行 $n$ 个整数，表示 $w_1, w_2, \dots, w_n$ 。

输出一个整数表示答案。

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

【样例解释 1】 对于 $a_1=0,a_2=1,a_3=1$，其排列有 $a_1=0,a_2=1,a_3=1$，是合法排列，排列的权值是 $1*5+2*7+3*3=28$； $a_2=1,a_1=0,a_3=$1，是非法排列，因为 $a_{p[1]}$等于 $p[2]$； $a_1=0,a_3=1,a_2=$1，是合法排列，排列的权值是 $1*5+2*3+3*7=32$； $a_3=1,a_1=0,a_2=1$，是非法排列，因为 $a_{p[1]}$等于 $p[2]$； $a_2=1,a_3=1,a_1=0$，是非法排列，因为 $a_{p[1]}$等于 $p[3]$； $a_3=1,a_2=1,a_1=0$，是非法排列，因为 $a_{p[1]}$等于 $p[3]$。 因此该题输出最大权值 $32$。 【样例解释 2】 对于 $a_1=2,a_2=3,a_3=1$，其排列有： $a_1=2,a_2=3,a_3=1$，是非法排列，因为 $a_{p[1]}$等于 $p[2]$； $a_2=3,a_1=2,a_3=1$，是非法排列，因为 $a_{p[1]}$等于 $p[3]$； $a_1=2,a_3=1,a_2=3$ ，是非法排列，因为 $a_{p[1]}$等于 $p[3]$； $a_3=1,a_1=2,a_2=3$ ，是非法排列，因为 $a_{p[2]}$等于 $p[3]$； $a_2=3,a_3=1,a_1=2$ ，是非法排列，因为 $a_{p[2]}$等于 $p[3]$； $a_3=1,a_2=3,a_1=2$ ，是非法排列，因为 $a_{p[1]}$等于 $p[3]$ 因此该题没有合法排列。 【数据范围】 对于前 $20\%$ 的数据，$1 \le n \le 10$。 对于前 $40\%$ 的数据，$1 \le n \le 15$。 对于前 $60\%$ 的数据，$1 \le n \le 1000$。 对于前 $80\%$ 的数据，$1 \le n \le 10^5$。 对于 $100\%$ 的数据，$1 \le n \le 5\times10^5$，$0 \le a_i \le n$，$1 \le w_i \le 10^9 $，所有$w_i$的和不超过 $1.5×10^{13}$。