一群 $$$n$$$ 舞者正在为闭幕式排练表演。舞者们排成一排,他们已经研究好了舞步,不能改变姿势。对于其中一些人来说,已经购买了白色的舞蹈服,对于其中一些人来说是黑色的,而对于其余的人,该服装将在将来购买。
买套装的那天,导演被告知,如果现场的套装颜色能够形成回文,那么奥运会的参赛者就会很高兴。回文是从左到右读取和从右到左读取时相同的序列。导演喜欢这个主意,她想购买服装,使最左边的舞者的衣服颜色与最右边的舞者的衣服颜色相同,左第二个与右第二个相同,依此类推。
导演知道买一套白色西装需要多少节,买一套黑色西装需要多少节。你需要找出是否可以购买西装来形成回文,如果可以,这样做的最低成本是多少。请记住,舞者不能改变位置,并且由于官僚原因,不允许为已有服装的舞者购买新服装,即使这会减少总体支出。
输入
第一行包含三个整数 $$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \leq n \leq 20$$$, $$$1 \leq a, b \leq 100$$$) — 舞者数量、白色套装的成本和黑色套装的成本。
下一行包含$$$n$$$数字$$$c_i$$$,其中$$$i$$$-表示第$$$i$$$个舞者的套装颜色。数字 $$$0$$$ 表示白色,$$$1$$$ — 黑色,$$$2$$$ 表示该舞者的套装仍有待购买。
输出
如果不交换舞者并为有舞者购买新套装就不可能形成回文,则输出-1。否则,输出最小的价格以获得想要的视觉效果。
示例
输入 #1
5 100 1 0 1 2 1 2
输出 #1
101
输入 #2
3 10 12 1 2 0
输出 #2
-1
输入 #3
3 12 1 0 1 0
输出 #3
0
注意
在第一个示例中,获得回文颜色的最便宜的方法是为左边第三个舞者购买黑色套装,为最右边的舞者购买白色套装。
在第二个示例中,最左边的舞者服装已经与最右边的舞者服装不同,因此无法获得所需的颜色。
在第三个示例中,所有套装都已购买,并且它们的颜色形成回文。