题目描述

题目译自 JOISC 2022 Day2 T1 「コピー & ペースト 3 / Copy and Paste 3」。译文由 hehezhou 友情提供。

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$ 最少要多少单位时间。

11
mississippi
10
5
2

88

16
aaaaaaaaaaaaaaaa
1
1
1

9

18
aababbbababbbaabbb
1000000000
100000
10000000

8060200000

数据范围与提示

对于所有数据，满足：

• $1\leq N\leq 2500$
• $S$ 是一个长度为 $N$ 的小写字母串。
• $1\leq A,B,C\leq 10^9$

详细子任务附加限制及分值如下表所示：