Contest Duration: - (local time) (100 minutes) Back to Home
C - Rotate and Palindrome /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

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

• A 円払う。 S の左端の文字を右端に移動する。すなわち、S_1S_2\ldots S_NS_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


入力例 1

5 1 2
rrefa


出力例 1

3


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

入力例 2

8 1000000000 1000000000
bcdfcgaa


出力例 2

4000000000


Score : 300 points

Problem Statement

You are given a string S of length N. Let S_i\ (1\leq i \leq N) be the i-th character of S from the left.

You may perform the following two kinds of operations zero or more times in any order:

• Pay A yen (the currency in Japan). Move the leftmost character of S to the right end. In other words, change S_1S_2\ldots S_N to S_2\ldots S_NS_1.

• Pay B yen. Choose an integer i between 1 and N, and replace S_i with any lowercase English letter.

How many yen do you need to pay to make S a palindrome?

What is a palindrome? A string T is a palindrome if and only if the i-th character from the left and the i-th character from the right are the same for all integers i (1 \le i \le |T|), where |T| is the length of T.

Constraints

• 1\leq N \leq 5000
• 1\leq A,B\leq 10^9
• S is a string of length N consisting of lowercase English letters.
• All values in the input except for S are integers.

Input

The input is given from Standard Input in the following format:

N A B
S


Output

Print the answer as an integer.

Sample Input 1

5 1 2
rrefa


Sample Output 1

3


First, pay 2 yen to perform the operation of the second kind once: let i=5 to replace S_5 with e. S is now rrefe.

Then, pay 1 yen to perform the operation of the first kind once. S is now refer, which is a palindrome.

Thus, you can make S a palindrome for 3 yen. Since you cannot make S a palindrome for 2 yen or less, 3 is the answer.

Sample Input 2

8 1000000000 1000000000
bcdfcgaa


Sample Output 2

4000000000


Note that the answer may not fit into a 32-bit integer type.