JOI, Ltd. 是一家以“奇思妙想的发明”而闻名的公司。最近，JOI, Ltd. 开发了一款名为“Just Odd Editor”的文本编辑器。

使用该文本编辑器，我们可以通过多次执行以下操作来输入一个字符串。设 $X$ 为文本编辑器屏幕上显示的字符串，设 $Y$ 为剪贴板中保存的字符串。最初，$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$ 单位时间。

你安装了 Just Odd Editor。你希望尽快输入一个长度为 $N$ 的字符串 $S$。通过执行操作，你希望尽快使屏幕上显示的字符串变为 $S$。

编写一个程序，给定长度 $N$、字符串 $S$ 以及执行各操作所需的单位时间，计算输入字符串 $S$ 所需的最少时间。

输入格式

从标准输入读取以下数据：

$N$ $S$ $A$ $B$ $C$

输出格式

输出一行到标准输出。输出应包含输入字符串 $S$ 所需的最少时间。

数据范围

• $1 \le N \le 2\,500$。
• $S$ 是一个长度为 $N$ 的字符串。$S$ 的每个字符都是小写英文字母（'a' - 'z'）。
• $1 \le A \le 1\,000\,000\,000$ ($= 10^9$)。
• $1 \le B \le 1\,000\,000\,000$ ($= 10^9$)。
• $1 \le C \le 1\,000\,000\,000$ ($= 10^9$)。
• $N, A, B, C$ 均为整数。

子任务

1. (1 分) $N = 3$。
2. (5 分) $S$ 的每个字符均为 'a'。
3. (14 分) $N \le 30$。
4. (10 分) $N \le 200$。
5. (32 分) $N \le 1\,000$。
6. (38 分) 无附加限制。

样例

样例输入 1

11
mississippi
10
5
2

样例输出 1

88

说明 1

通过执行一系列操作，我们可以在 88 单位时间内输入 mississippi。由于这是输入 mississippi 所需的最少时间，因此输出 88。

样例输入 2

16
aaaaaaaaaaaaaaaa
1
1
1

样例输出 2

9

说明 2

通过执行一系列操作，我们可以在 9 单位时间内输入 aaaaaaaaaaaaaaaa。由于这是输入 aaaaaaaaaaaaaaaa 所需的最少时间，因此输出 9。

样例输入 3

18
aababbbababbbaabbb
1000000000
100000
10000000

样例输出 3

8060200000