题目描述

给定 $n$ 个整数 $a_1, a_2, \dots, a_n, 0 \le ai \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]$等于 $ap[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$ 。

输出格式

输出一个整数表示答案

样例 #1

样例输入 #1

3 
0 1 1 
5 7 3

样例输出 #1

32

样例 #2

样例输入 #2

3 
2 3 1 
1 2 3

样例输出 #2

-1

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

提示

【样例解释 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 100000$。

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

https://www.luogu.com.cn/paste/pol3qj7x