#F5. 宝石项链

宝石项链

T1 宝石项链(necklace)

时间限制:1.0 秒 空间限制:256 MB

题目描述

小 S 有一条由 nn 颗宝石串成的环形项链,宝石编号为 1,2,…,n1,2,\dots,n。第 ii 颗宝石的颜色为 ai∈{0,1}a_i\in\{0,1\}。编号在模 nn 意义下相邻,即 11 与 22 相邻,22 与 33 相邻,…\dots,n−1n-1 与 nn 相邻,nn 与 11 相邻。

小 S 可以进行任意次如下操作:选择一颗宝石 ii,同时翻转宝石 i−1,i,i+1i-1,i,i+1 的颜色(下标在模 nn 意义下计算)。若同一种颜色在一次操作中被翻转多次,则每次都会改变颜色(翻转两次等于不变)。第 ii 颗宝石被选择一次需要支付 cic_i 的代价;同一颗宝石可以被选择多次,每次都要支付代价。

小 S 希望最终所有宝石的颜色相同(全部为 00 或全部为 11)。请你求出最小总代价;如果无论如何都无法做到,输出 −1-1。

输入格式

第一行一个正整数 nn。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n。

第三行 nn 个正整数 c1,c2,…,cnc_1,c_2,\dots,c_n。

输出格式

输出一行一个整数,表示最小总代价;若无解,输出 −1-1。

样例 1

输入:

4
1 0 1 0
5 1 2 3

输出:

4

样例 1 解释: 选择第 22 颗和第 44 颗宝石各操作一次,总代价为 c2+c4=1+3=4c_2+c_4=1+3=4。两次操作后所有宝石都变成颜色 11,可以证明不存在更小的代价。

样例 2

输入:

6
1 0 0 0 0 0
1 1 1 1 1 1

输出:

-1

样例 2 解释: 当 nn 是 33 的倍数时,三个同余类(下标模 33)中颜色 11 的个数的奇偶性必须相同,否则无解。这里三个同余类中颜色 11 的个数分别为 1,0,01,0,0,奇偶性不同,因此无解。

数据范围

对于全部测试数据:1≤n≤1061\le n\le 10^6;ai∈{0,1}a_i\in\{0,1\};1≤ci≤1091\le c_i\le 10^9。

子任务

子任务 分值 特殊限制
1 20 n≤20n\le 20
2 所有 ci=1c_i=1
3 n mod 3≠0n\bmod 3\ne 0
4 40 无特殊限制

提示: 答案可能超过 231−12^{31}-1,请使用 6464 位整数。