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}$
鄂公网安备 42010202000505 号