题目描述

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

---

样例 1

输入

11
mississippi
10
5
2

输出

88

最优操作序列

轮次	操作	解释	X	Y	代价	总时间
-			""	""	-	0
1	操作 A	输入字符	"s"		10
2	操作 B	全选并剪切	""	"s"	5	15
3	操作 C	在尾部粘贴	"s"		2	17
4			"ss"			19
5	操作 A	输入字符	"ssi"		10	29
6	操作 B	全选并剪切	""	"ssi"	5	34
7	操作 A	输入字符	"m"		10	44
8			"mi"			54
9	操作 C	在尾部粘贴	"missi"		2	56
10			"mississi"			58
11	操作 A	输入字符	"mississip"		10	68
12			"mississipp"			78
13			"mississippi"			88

这组样例满足子任务 $3$、$4$、$5$、$6$ 的限制。

---

样例 2

输入

16
aaaaaaaaaaaaaaaa
1
1
1

输出

9

最优操作序列

轮次	操作	解释	X	Y	代价	总时间
-			""	""	-	0
1	操作 A	输入字符	"a"		1	1
2			"aa"			2
3			"aaa"			3
4			"aaaa"			4
5	操作 B	全选并剪切	""	"aaaa"		5
6	操作 C	在尾部粘贴	"aaaa"			6
7			"aaaaaaaa"			7
8			"aaaaaaaaaaaa"			8
9			"aaaaaaaaaaaaaaaa"			9

这组样例满足子任务 $2$、$3$、$4$、$5$、$6$ 的限制。

---

样例 3

输入

18
aababbbababbbaabbb
1000000000
100000
10000000

输出

8060200000

这组样例满足子任务 $3$、$4$、$5$、$6$ 的限制。

---

数据范围与提示

对于所有数据，满足：

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

子任务分值表

子任务编号	附加限制	分数
1	$N = 3$	1
2	$S$ 只包含字符 $\texttt{a}$	5
3	$N \leq 30$	14
4	$N \leq 200$	10
5	$N \leq 1000$	32
6	无附加限制	38