2509 「AHOI / HNOI2018」排列

给定 $n$ 个整数 $a_1, a_2, \ldots , a_n(0 \le a_i \le n)$，以及 $n$ 个整数 $w_1, w_2, …, w_n$。称 $a_1, a_2, \ldots , a_n$ 的一个排列 $a_{p[1]}, a_{p[2]}, \ldots , a_{p[n]}$ 为 $a_1, a_2, \ldots , 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]} + \ldots + nw_{p[n]}$。你需要求出在所有合法排列中的最大权值。如果不存在合法排列，输出 $-1$。

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

第一行一个整数 $n$。

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

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

输出一个整数表示答案。

对于 $a_1=0,a_2=1,a_3=1$，其排列有 * $a_1=0,a_2=1,a_3=1$，是合法排列，排列的权值是 $15+27+33=28$； * $a_2=1,a_1=0,a_3=1$，是非法排列，因为 $a_{p[1]}$ 等于 $p[2]$； * $a_1=0,a_3=1,a_2=1$，是合法排列，排列的权值是 $15+23+37=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$。

对于 $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 100000$；

对于 $100\%$ 的数据，$1 \le n \le 500000$，$0 \le a_i \le n (1 \le i \le n)$，$1 \le w_i \le 10^9$ ，所有 $w_i$ 的和不超过 $1.5 \times 10^{13}$。