配点 : $300$ 点

問題文

長さ $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$ を回文にするためには最低で何円必要ですか？

制約

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

入力

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

$N$ $A$ $B$

$S$

出力

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

5 1 2
rrefa

3

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

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

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

8 1000000000 1000000000
bcdfcgaa

4000000000

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