描述
给定一个长度为n的数组a,其中每个元素a_i表示第i个位置的颜色。颜色可以是0(白色)、1(黑色)或2(未确定)。你需要将未确定的位置(颜色为2)填充为0或1,使得整个数组成为一个回文数组。回文数组是指数组从前往后读和从后往前读是一样的。
填充未确定的位置需要花费一定的成本:将位置填充为0的成本为a,填充为1的成本为b。请问完成填充的最小成本是多少?
输入
第一行包含三个整数n、a和b,分别表示数组的长度、填充为0的成本和填充为1的成本。 第二行包含n个整数a_1,a_2,…,a_n,表示每个位置的颜色。
对于100%的数据:
1\le n \le 20
1\le a,b \le 100
输出
输出一个整数,表示完成填充的最小成本。如果无法将数组填充为回文数组,则输出-1。
样例
输入
5 100 1 0 1 2 1 2
输出
101
输入
3 10 12 1 2 0
输出
-1
输入
3 12 1 0 1 0
输出
0