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

以下是一组最优操作：

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

样例二

input

16
aaaaaaaaaaaaaaaa
1
1
1

output

9

explanation

一组最优策略如下：

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

样例三

input

18
aababbbababbbaabbb
1000000000
100000
10000000

output

8060200000

explanation

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

数据范围与提示

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

Subtasks

1. $\text{(1 points) }N=3$
2. $\text{(5 points)}$ $S$ 只包含字符 a。
3. $\text{(14 points) }N\le 30$
4. $\text{(10 points) }N\le 200$
5. $\text{(32 points) }N\le 1000$
6. $\text{(38 points)}$ 无特殊限制。

时间限制：$\mathtt{\text{3s}}$

空间限制：$\mathtt{\text{2GB}}$