← 返回题目列表

AtCoder · abc286_c

E. 旋转和回文

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个字符串 S 长度 N。 让 S_i\ (1\leq i \leq N) 是 i- 第一个字符 S 从左边开始。

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

  • 支付 A 日元(日本货币)。 移动最左边的字符 S 到右端。 换句话说,改变 S_1S_2\ldots S_N to S_2\ldots S_NS_1.

  • 支付 B 日元。 选择一个整数 i 之间 1 和 N,并替换 S_i 与任何小写英文字母。

您需要支付多少日元才能制作 S 回文?

什么是回文? 一个字符串 T 是回文当且仅当 i从左边数第一个字符和 i从右边算起的第一个字符对于所有整数都是相同的 i (1 \le i \le |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,这是一个回文。

因此,您可以使 S 回文 3 日元。 既然你无法使 S 回文 2 日元或更少, 3 就是答案。


示例输入 2

8 1000000000 1000000000
bcdfcgaa

示例输出 2

4000000000

请注意,答案可能不适合 32- 位整数类型。