题目背景

JOISC2022 D2T1

题目描述

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】

以下是一组最优操作：

轮次	操作	解释	$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】

一组最优策略如下：

轮次	操作	解释	$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】

这组样例满足子任务 $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\le 30$	$14$
$4$	$N\le 200$	$10$
$5$	$N \le 1000$	$32$
$6$	无附加限制	$38$