200302 : 回文成本
描述

给定一个长度为n的数组a,其中每个元素a_i表示第i个位置的颜色。颜色可以是0(白色)、1(黑色)或2(未确定)。你需要将未确定的位置(颜色为2)填充为01,使得整个数组成为一个回文数组。回文数组是指数组从前往后读和从后往前读是一样的。

填充未确定的位置需要花费一定的成本:将位置填充为0的成本为a,填充为1的成本为b。请问完成填充的最小成本是多少?

输入

第一行包含三个整数nab,分别表示数组的长度、填充为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
语言:
主题: