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