AT_abc286_c [ABC286C] Rotate and Palindrome

[problemUrl]: https://atcoder.jp/contests/abc286/tasks/abc286_c 長さ $ 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 $

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

### 制約 - $ 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 整数に収まらない場合があることに注意してください。