题目描述

長さ $N$ の文字列 $S$ が与えられます。$S_i\ (1\leq\ i\ \leq\ N)$ を $S$ の左から $i$ 番目の文字とします。

あなたは以下の $2$ 種類の操作を好きな順番で $0$ 回以上好きな回数行うことができます。

• $A$ 円払う。 $S$ の左端の文字を右端に移動する。すなわち、$S_1S_2\ldots\ S_N$ を $S_2\ldots\ S_NS_1$ に変える。
• $B$ 円払う。 $1$ 以上 $N$ 以下の整数 $i$ を選び、 $S_i$ を好きな英小文字で置き換える。

$S$ を回文にするためには最低で何円必要ですか？

回文とは ある文字列 $T$ について、 $T$ の長さを $|T|$ として、全ての整数 $i$ ($1\ \le\ i\ \le\ |T|$) について、 $T$ の前から $i$ 文字目と後ろから $i$ 文字目が同じであるとき、またそのときに限って、 $T$ は回文です。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A$ $B$ $S$

输出格式

答えを整数として出力せよ。

题目大意

给出一个字符串，有两种操作：

• 花费 A ，把串的第一位放到最后一位
• 花费 B ，修改串的一个字母

求把原串变成回文串的最小代价。

输入： 先输入 $n,A,B$ ，第二行字符串 $S$

5 1 2
rrefa

3

8 1000000000 1000000000
bcdfcgaa

4000000000

提示

制約

• $1\leq\ N\ \leq\ 5000$
• $1\leq\ A,B\leq\ 10^9$
• $S$ は英小文字からなる長さ $N$ の文字列
• $S$ 以外の入力は全て整数

Sample Explanation 1

最初に $2$ 番目の操作を $1$ 回行います。$2$ 円払い、$i=5$ として $S_5$ を e で置き換えます。 $S$ は rrefe となります。 次に $1$ 番目の操作を $1$ 回行います。$1$ 円払い、$S$ は refer となります。これは回文です。 よって $3$ 円払うことで $S$ を回文にすることができました。 $2$ 円以下払うことで $S$ を回文にすることは不可能なので、これが答えです。

Sample Explanation 2

答えは $32$ bit 整数に収まらない場合があることに注意してください。