JOI 公司是一家以“没啥用发明”而闻名的公司。最近,JOI 公司开发了一款名为“没啥用编辑器”的编辑器。
在这个编辑器中,可以执行如下几种操作来输入某个字符串,设 $X$ 为屏幕上的字符串,$Y$ 为剪切板中的字符串,初始均为空串:
- 操作 A:输入字符 $c$,即将 $X$ 更新为 $X+c$。
- 操作 B:选择所有字符并剪切,即将 $Y$ 更新为 $X$,并将 $X$ 置为空串。
- 操作 C:将剪切板中的字符串粘贴到当前字符串末尾,即将 $X$ 更新为 $X+Y$。
对于字符串或字符 $x,y$,$x+y$ 表示将 $x$ 和 $y$ 顺次拼接得到的结果。使用一次操作 A,B,C 分别要花费 $A,B,C$ 单位时间。
你安装了“没啥用编辑器”,并想要尽可能快地输入一个长度为 $N$ 的字符串 $S$。
你需要计算出最少需要花费多少时间。
输入格式
第一行一个整数 $N$ 表示字符串长度。
第二行一个长度为 $N$ 的字符串 $S$ 表示要输入的字符串。
第三行一个整数 $A$ 表示操作 A 的代价。
第四行一个整数 $B$ 表示操作 B 的代价。
第五行一个整数 $C$ 表示操作 C 的代价。
输出格式
一行一个整数表示输入字符串 $S$ 最少要多少单位时间。
样例一
input
11 mississippi 10 5 2
output
88
explanation
以下是一组最优操作:
轮次 | 操作 | 解释 | $X$ | $Y$ | 代价 | 总时间 |
---|---|---|---|---|---|---|
- | - | - | "" |
"" |
- | $0$ |
$1$ | 操作 A | 输入字符 | "s" |
"" |
$10$ | $10$ |
$2$ | 操作 B | 全选并剪切 | "" |
"s" |
$5$ | $15$ |
$3$ | 操作 C | 在尾部粘贴 | "s" |
"s" |
$2$ | $17$ |
$4$ | 操作 C | 在尾部粘贴 | "ss" |
"s" |
$2$ | $19$ |
$5$ | 操作 A | 输入字符 | "ssi" |
"s" |
$10$ | $29$ |
$6$ | 操作 B | 全选并剪切 | "" |
"ssi" |
$5$ | $34$ |
$7$ | 操作 A | 输入字符 | "m" |
"ssi" |
$10$ | $44$ |
$8$ | 操作 A | 输入字符 | "mi" |
"ssi" |
$10$ | $54$ |
$9$ | 操作 C | 在尾部粘贴 | "missi" |
"ssi" |
$2$ | $56$ |
$10$ | 操作 C | 在尾部粘贴 | "mississi" |
"ssi" |
$2$ | $58$ |
$11$ | 操作 A | 输入字符 | "mississip" |
"ssi" |
$10$ | $68$ |
$12$ | 操作 A | 输入字符 | "mississipp" |
"ssi" |
$10$ | $78$ |
$13$ | 操作 A | 输入字符 | "mississippi" |
"ssi" |
$10$ | $88$ |
这组样例满足子任务 $3,4,5,6$ 的限制。
样例二
input
16 aaaaaaaaaaaaaaaa 1 1 1
output
9
explanation
一组最优策略如下:
轮次 | 操作 | 解释 | $X$ | $Y$ | 代价 | 总时间 |
---|---|---|---|---|---|---|
- | - | - | "" |
"" |
- | $0$ |
$1$ | 操作 A | 输入字符 | "a" |
"" |
$1$ | $1$ |
$2$ | 操作 A | 输入字符 | "aa" |
"" |
$1$ | $2$ |
$3$ | 操作 A | 输入字符 | "aaa" |
"" |
$1$ | $3$ |
$4$ | 操作 A | 输入字符 | "aaaa" |
"" |
$1$ | $4$ |
$5$ | 操作 B | 全选并剪切 | "" |
"aaaa" |
$1$ | $5$ |
$6$ | 操作 C | 在尾部粘贴 | "aaaa" |
"aaaa" |
$1$ | $6$ |
$7$ | 操作 C | 在尾部粘贴 | "aaaaaaaa" |
"aaaa" |
$1$ | $7$ |
$8$ | 操作 C | 在尾部粘贴 | "aaaaaaaaaaaa" |
"aaaa" |
$1$ | $8$ |
$9$ | 操作 C | 在尾部粘贴 | "aaaaaaaaaaaaaaaa" |
"aaaa" |
$1$ | $9$ |
这组样例满足子任务 $2,3,4,5,6$ 的限制。
样例三
input
18 aababbbababbbaabbb 1000000000 100000 10000000
output
8060200000
explanation
这组样例满足子任务 $3,4,5,6$ 的限制。
数据范围与提示
- $1\leq N\leq 2500$
- $S$ 是一个长度为 $N$ 的小写字母串。
- $1\leq A,B,C\leq 10^9$
Subtasks
- $\text{(1 points) }N=3$
- $\text{(5 points)}$ $S$ 只包含字符
a
。 - $\text{(14 points) }N\leq 30$
- $\text{(10 points) }N\leq 200$
- $\text{(32 points) }N\leq 1000$
- $\text{(38 points)}$ 无特殊限制。
时间限制:$\texttt{3s}$
空间限制:$\texttt{2GB}$