旋转与回文

题目描述

给定长度为 $N$ 的字符串 $S$。设 $S_i\ (1 \le i \le N)$ 为 $S$ 从左数第 $i$ 个字符。

你可以按任意顺序进行以下两种操作各任意次(也可以不进行):

• 花费 $A$ 日元:将 $S$ 最左边的字符移到最右边。换句话说,把 $S_1S_2\ldots S_N$ 变为 $S_2\ldots S_NS_1$。
• 花费 $B$ 日元:选择 $1$ 到 $N$ 之间的整数 $i$,将 $S_i$ 替换为任意小写英文字母。

要使 $S$ 成为回文,最少需要花费多少日元?

什么是回文?

字符串 $T$ 是回文,当且仅当对于所有整数 $i$ ($1 \le i \le |T|$),从左数第 $i$ 个字符和从右数第 $i$ 个字符相同,其中 $|T|$ 是 $T$ 的长度。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

将答案作为整数输出。

样例

5 1 2
rrefa

3

首先,花费 $2$ 日元进行第二种操作一次:令 $i=5$,把 $S_5$ 替换为 e。此时 $S$ 变为 rrefe。

然后,花费 $1$ 日元进行第一种操作一次。此时 $S$ 变为 refer,是回文。

因此,可以用 $3$ 日元使 $S$ 成为回文。由于无法用 $2$ 日元或更少的花费使 $S$ 成为回文,答案为 $3$。

8 1000000000 1000000000
bcdfcgaa

4000000000

注意,答案可能超出 $32$ 位整数类型的范围。

数据范围

• $1 \le N \le 5000$
• $1 \le A,B \le 10^9$
• $S$ 是由小写英文字母组成的长度为 $N$ 的字符串。
• 输入中除 $S$ 以外的所有值均为整数。