给定n个整数a1, a2, ..., an,0 ≤ ai ≤ n,以及n个整数w1, w2, ..., wn。称a1, a2, ..., an的 一个排列 ap[1], ap[2], ..., ap[n]为 a1, a2, ..., an 的一个合法排列,当且仅当该排列满足:对于任意 的 k 和任意的 j,如果 j<=k,那么 ap[j]不等于 p[k]。(换句话说就是:对于任意的 k 和任意的 j,如果 p[k]等于 ap[j],那么 k<j。)定义这个合法排列的权值为 wp[1] + 2wp[2] + ... + nwp[n]。你 需要求出在所有合法排列中的最大权值。如果不存在合法排列,输出-1。
样例解释中给出了合法排列和非法排列的实例。

第一行一个整数 n。
接下来一行 n 个整数,表示 a1, a2,...,an。
接下来一行n 个整数,表示w1,w2,...,wn。

输出一个整数表示答案。

【样例解释 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 ≤ 109 ,所有wi的和不超过 1.5×10^13。

贪心 AHOI高中 2018 level9