该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

给定一个长度为 $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$ 变为回文串所需的最小花费。

样例输入

5 1 2
rrefa

样例输出

3

样例输入

8 1000000000 1000000000
bcdfcgaa

样例输出

4000000000

说明

样例1解释

首先进行第 $2$ 种操作 $1$ 次，支付 $2$ 元，将 $i=5$ 的 $S_5$ 替换为 e，此时 $S$ 变为 rrefe。接着进行第 $1$ 种操作 $1$ 次，支付 $1$ 元，$S$ 变为 refer，这是一个回文串。因此，最少支付 $3$ 元即可将 $S$ 变为回文串。无法用 $2$ 元或更少的花费将 $S$ 变为回文串，所以答案是 $3$。

数据范围

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