AT_abc286_c [ABC286C] Rotate and Palindrome

给定一个长度为 $N$ 的字符串 $S$。记 $S_i\ (1\leq i \leq N)$ 为 $S$ 从左往右的第 $i$ 个字符。 你可以以任意顺序、任意次数（包括 $0$ 次）进行以下两种操作： - 支付 $A$ 元，将 $S$ 的最左端字符移动到最右端。也就是说，将 $S_1S_2\ldots S_N$ 变为 $S_2\ldots S_N S_1$。 - 支付 $B$ 元，选择一个 $1$ 到 $N$ 之间的整数 $i$，并将 $S_i$ 替换为任意一个小写英文字母。 请问，最少需要支付多少元才能将 $S$ 变为回文串？ 回文串的定义如下：对于某个字符串 $T$，记其长度为 $|T|$，当且仅当对于所有整数 $i$（$1\leq i\leq |T|$），$T$ 的第 $i$ 个字符与倒数第 $i$ 个字符相同，$T$ 才是回文串。

输入以如下格式从标准输入读入。 > $N$ $A$ $B$ $S$

请输出一个整数，表示将 $S$ 变为回文串所需的最小花费。

## 限制条件 - $1\leq N \leq 5000$ - $1\leq A,B\leq 10^9$ - $S$ 是由小写英文字母组成的长度为 $N$ 的字符串 - 除 $S$ 外的所有输入均为整数 ## 样例解释 1 首先进行第 $2$ 种操作 $1$ 次，支付 $2$ 元，将 $i=5$ 的 $S_5$ 替换为 `e`，此时 $S$ 变为 `rrefe`。接着进行第 $1$ 种操作 $1$ 次，支付 $1$ 元，$S$ 变为 `refer`，这是一个回文串。因此，最少支付 $3$ 元即可将 $S$ 变为回文串。无法用 $2$ 元或更少的花费将 $S$ 变为回文串，所以答案是 $3$。 ## 样例解释 2 请注意，答案可能超过 $32$ 位整数的范围。 由 ChatGPT 4.1 翻译