Score : $300$ points

问题描述

给定一个长度为 $N$ 的字符串 $S$。令 $S_i\ (1\leq i \leq N)$ 表示从左数起第 $i$ 个字符。

你可以按任意顺序执行以下两种操作零次或多次：

• 花费 $A$ 日元（日本货币）。将 $S$ 的最左侧字符移动到右侧末尾。换句话说，将 $S_1S_2\ldots S_N$ 改变为 $S_2\ldots S_NS_1$。

• 花费 $B$ 日元。选择一个整数 $i$ （$1$ 到 $N$ 之间），并将 $S_i$ 替换为任意小写英文字母。

你需要支付多少日元才能使 $S$ 变成回文串？

什么是回文串？字符串 $T$ 是回文串当且仅当对于所有整数 $i$（$1 \le i \le |T|$），从左数起第 $i$ 个字符与从右数起第 $i$ 个字符相同，其中 $|T|$ 表示 $T$ 的长度。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

update @ 2024/3/10 11:57:22