假设给你一个长度为 $$$n$$$ 的字符串 $$$s$$$,由小写英文字母组成。您需要使用尽可能少的硬币来压缩它。
要压缩字符串,必须将 $$$s$$$ 表示为多个非空字符串的串联:$$$s = t_{1} t_{2} \ldots t_{k}$$$。这些字符串中的第 $$$i$$$ 应使用以下两种方式之一进行编码:
- 如果 $$$|t_{i}| = 1$$$,表示当前字符串由单个字符组成,您可以支付$$$a$$$硬币对其进行编码;
- 如果 $$$t_{i}$$$ 是 $$$t_{1} t_{2} \ldots t_{i - 1}$$$ 的子字符串,那么您可以支付 $$$b$$$ 硬币对其进行编码。
字符串 $$$x$$$ 是字符串 $$$y$$$ 的子字符串,如果 $$$x$$$ 可以通过删除开头的几个(可能是零个或全部)字符和结尾的几个(可能是零个或全部)字符从 $$$y$$$ 获得。
因此,您的任务是计算压缩给定字符串 $$$s$$$ 所需花费的最小可能数量的硬币。
输入
第一行包含三个正整数,用空格分隔:$$$n$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \leq n, a, b \leq 5000$$$) — 字符串的长度、压缩单字符字符串的成本和压缩之前出现的字符串的成本。
第二行包含单个字符串$$$s$$$,由$$$n$$$小写英文字母组成。
输出
输出一个整数——压缩 $$$s$$$ 所需花费的最小可能数量的硬币。
示例
输入 #1
3 3 1 aba
输出 #1
7
输入 #2
4 1 1 abcd
输出 #2
4
输入 #3
4 10 1 aaaa
输出 #3
12
注意
在第一个示例案例中,您可以设置 $$$t_{1} =$$$ 'a', $$$t_{2} =$$$ 'b', $$$t_{3} =$$$ 'a' 并支付 $$$3 + 3 + 1 = 7$$$ 硬币,因为 $$$t_{3}$$$ 是$$$t_{1}t_{2}$$$。
在第二个示例中,您只需单独压缩每个字符。
在第三个示例中,您设置 $$$t_{1} = t_{2} =$$$ 'a', $$$t_{3} =$$$ 'aa' 并支付 $$$10 + 1 + 1 = 12$$$ 硬币,因为 $$$t_{2}$$$ 是 $$$t_{1}$$$ 的子字符串,并且$$$t_{3}$$$ 是 $$$t_{1} t_{2}$$$ 的子字符串。