[HNOI/AHOI2018]排列

题目描述

给定 $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

输入输出格式

输入格式


第一行一个整数 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

输入样例 #2

3 
2 3 1 
1 2 3 

输出样例 #2

-1

输入样例 #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】 对于 a1=0,a2=1,a3=1,其排列有 a1=0,a2=1,a3=1,是合法排列,排列的权值是 1\*5+2\*7+3\*3=28; a2=1,a1=0,a3=1,是非法排列,因为 ap[1]等于 p[2]; a1=0,a3=1,a2=1,是合法排列,排列的权值是 1\*5+2\*3+3\*7=32; a3=1,a1=0,a2=1,是非法排列,因为 ap[1]等于 p[2]; a2=1,a3=1,a1=0,是非法排列,因为 ap[1]等于 p[3]; a3=1,a2=1,a1=0,是非法排列,因为 ap[1]等于 p[3]。 因此该题输出最大权值 32。 【样例解释 2】 对于 a1=2,a2=3,a3=1,其排列有: a1=2,a2=3,a3=1,是非法排列,因为 ap[1]等于 p[2]; a2=3,a1=2,a3=1,是非法排列,因为 ap[1]等于 p[3]; a1=2,a3=1,a2=3,是非法排列,因为 ap[1]等于 p[3]; a3=1,a1=2,a2=3,是非法排列,因为 ap[2]等于 p[3]; a2=3,a3=1,a1=2,是非法排列,因为 ap[2]等于 p[3]; a3=1,a2=3,a1=2,是非法排列,因为 ap[1]等于 p[3]。 因此该题没有合法排列。 【数据范围】 对于前20% 的数据,1≤n≤ 10。 对于前40% 的数据,1≤n ≤ 15。 对于前60% 的数据,1≤n ≤1000。 对于前80% 的数据,1≤n ≤100000。 对于100% 的数据,1≤n ≤ 500000,0 ≤ ai ≤ n,1 ≤ wi ≤ 10^9 ,所有wi的和不超过 1.5×10^13。