题目描述

给定长度为 $N$ 的字符串 $S$。记 $S_i\\ (1\\leq i \\leq N)$ 为 $S$ 左起第 $i$ 个字符。

你可以以任意顺序进行下面两种操作中的零次或多次：

• 支付 ¥A（日元）。将 $S$ 最左边的字符移到最右边。换句话说，将 $S_1S_2\\ldots S_N$ 变为 $S_2\\ldots S_NS_1$。

• 支付 ¥B。选择一个在 $1$ 和 $N$ 之间的整数 $i$，将 $S_i$ 替换为任意小写英文字母。

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

什么是回文串？当且仅当对于所有整数 $i$ ($1 \\le i \\le |T|$) 都有 $T$ 左起第 $i$ 个字符和右起第 $i$ 个字符相同，其中 $|T|$ 是 $T$ 的长度，那么字符串 $T$ 就是一个回文串。

约束条件

• $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

首先，支付 ¥2 进行一次第二种操作：选择 $i=5$ 将 $S_5$ 替换为 e。$S$ 变为 rrefe。

然后，支付 ¥1 进行一次第一种操作。$S$ 变为 refer，它是一个回文串。

因此，你可以支付 ¥3 将 $S$ 变为回文串。由于你无法用 ¥2 或更少的金额将 $S$ 变为回文串，所以答案为 3。

示例输入2

8 1000000000 1000000000
bcdfcgaa

示例输出2

4000000000

请注意，答案可能超出 32 位整数类型的表示范围。