#2509. 「AHOI / HNOI2018」排列

给定 $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\left[1\right]},a_{p\left[2\right]},\dots ,a_{p\left[n\right]}$ 为 $a_1,a_2,\dots ,a_n$ 的一个合法排列，当且仅当该排列满足：对于任意的 $k$ 和任意的 $j$，如果 $j\le k$，那么 ap[j]a_{p[j]}a​p[j]​​ 不等于 $p[k]$。（换句话说就是：对于任意的 $k$ 和任意的 $j$，如果 $p[k]$ 等于 ap[j]a_{p[j]}a​p[j]​​，那么 $k<j$。）

定义这个合法排列的权值为 $w_{p\left[1\right]}+2w_{p\left[2\right]}+\dots +n{w}_{p\left[n\right]}$。你需要求出在所有合法排列中的最大权值。如果不存在合法排列，输出 $-1$。

样例解释中给出了合法排列和非法排列的实例。

第一行一个整数 $n$。

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

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

输出一个整数表示答案。

样例输入 1

3
0 1 1
5 7 3

样例输出 1

32

样例解释 1

对于 a1=0,a2=1,a3=1a_1=0,a_2=1,a_3=1a​1​​=0,a​2​​=1,a​3​​=1，其排列有

• a1=0,a2=1,a3=1a_1=0,a_2=1,a_3=1a​1​​=0,a​2​​=1,a​3​​=1，是合法排列，排列的权值是 $1\ast 5+2\ast 7+3\ast 3=28$；
• a2=1,a1=0,a3=1a_2=1,a_1=0,a_3=1a​2​​=1,a​1​​=0,a​3​​=1，是非法排列，因为 ap[1]a_{p[1]}a​p[1]​​ 等于 $p[2]$；
• a1=0,a3=1,a2=1a_1=0,a_3=1,a_2=1a​1​​=0,a​3​​=1,a​2​​=1，是合法排列，排列的权值是 $1\ast 5+2\ast 3+3\ast 7=32$；
• a3=1,a1=0,a2=1a_3=1,a_1=0,a_2=1a​3​​=1,a​1​​=0,a​2​​=1，是非法排列，因为 ap[1]a_{p[1]}a​p[1]​​ 等于 $p[2]$；
• a2=1,a3=1,a1=0a_2=1,a_3=1,a_1=0a​2​​=1,a​3​​=1,a​1​​=0，是非法排列，因为 ap[1]a_{p[1]}a​p[1]​​ 等于 $p[3]$；
• a3=1,a2=1,a1=0a_3=1,a_2=1,a_1=0a​3​​=1,a​2​​=1,a​1​​=0，是非法排列，因为 ap[1]a_{p[1]}a​p[1]​​ 等于 $p[3]$。

因此该题输出最大权值 $32$。

样例输入 2

3
2 3 1
1 2 3

样例输出 2

-1

样例解释 2

对于 a1=2,a2=3,a3=1a_1=2,a_2=3,a_3=1a​1​​=2,a​2​​=3,a​3​​=1，其排列有：

• a1=2,a2=3,a3=1a_1=2,a_2=3,a_3=1a​1​​=2,a​2​​=3,a​3​​=1，是非法排列，因为 ap[1]a_{p[1]}a​p[1]​​ 等于 $p[2]$；
• a2=3,a1=2,a3=1a_2=3,a_1=2,a_3=1a​2​​=3,a​1​​=2,a​3​​=1，是非法排列，因为 ap[1]a_{p[1]}a​p[1]​​ 等于 $p[3]$；
• a1=2,a3=1,a2=3a_1=2,a_3=1,a_2=3a​1​​=2,a​3​​=1,a​2​​=3，是非法排列，因为 ap[1]a_{p[1]}a​p[1]​​ 等于 $p[3]$；
• a3=1,a1=2,a2=3a_3=1,a_1=2,a_2=3a​3​​=1,a​1​​=2,a​2​​=3，是非法排列，因为 ap[2]a_{p[2]}a​p[2]​​ 等于 $p[3]$；
• a2=3,a3=1,a1=2a_2=3,a_3=1,a_1=2a​2​​=3,a​3​​=1,a​1​​=2，是非法排列，因为 ap[2]a_{p[2]}a​p[2]​​ 等于 $p[3]$；
• a3=1,a2=3,a1=2a_3=1,a_2=3,a_1=2a​3​​=1,a​2​​=3,a​1​​=2，是非法排列，因为 ap[1]a_{p[1]}a​p[1]​​ 等于 $p[3]$。

因此该题没有合法排列。

样例输入 3

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

样例输出 3

809

对于前 $20\%$ 的数据，$1\le n\le 10$；

对于前 $40\%$ 的数据，$1\le n\le 15$；

对于前 $60\%$ 的数据，$1\le n\le 1000$；

对于前 $80\%$ 的数据，$1\le n\le 100000$；

对于 $100\%$ 的数据，$1\le n\le 500000$，0≤ai≤n(1≤i≤n)0 \le a_i \le n (1 \le i \le n)0≤a​i​​≤n(1≤i≤n)，1≤wi≤1091 \le w_i \le 10^91≤w​i​​≤10​9​​ ，所有 wiw_iw​i​​ 的和不超过 1.5×10131.5 \times 10^{13}1.5×10​13​​。