問題文

長さ $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$ は回文です。

制約

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

入力

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

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

出力

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

入力例 1

5 1 2
rrefa

出力例 1

3

最初に $2$ 番目の操作を $1$ 回行います。$2$ 円払い、$i=5$ として $S_5$ を e で置き換えます。 $S$ は rrefe となります。

次に $1$ 番目の操作を $1$ 回行います。$1$ 円払い、$S$ は refer となります。これは回文です。

よって $3$ 円払うことで $S$ を回文にすることができました。 $2$ 円以下払うことで $S$ を回文にすることは不可能なので、これが答えです。

入力例 2

8 1000000000 1000000000
bcdfcgaa

出力例 2

4000000000

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