本题没有可用的提交语言。

题目描述

给定 $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\times 5+2\times 7+3\times 3=28$；
• $a_2=1,a_1=0,a_3=1$，是非法排列，因为 $a_{p_2}$ 等于 $p_2$；
• $a_1=0,a_3=1,a_2=1$，是合法排列，排列的权值是 $1\times 5+2\times 3+3\times 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\le10^9$，所有 $w_i$ 的和不超过 $1.5×10^{13}$。