U210810 [JOISC 2022 Day 2] 复制粘贴 3 (Copy and Paste 3)

**译自 [JOISC 2022](https://www.ioi-jp.org/camp/2022/2022-sp-tasks/index.html) Day 2 T1 「[コピー & ペースト 3](https://www.ioi-jp.org/camp/2022/2022-sp-tasks/contest2/copypaste3.pdf) / [Copy and Paste 3](https://www.ioi-jp.org/camp/2022/2022-sp-tasks/contest2/copypaste3-en.pdf)」。** 此处仅有部分测试数据（每个包前一半数据），且原题时空限制为 3s,2GB，此处略有缩小。

定义字符串加法 $A+B$ 为按顺序连接这两个字符串。 你初始有两个空字符串 $X$ （文本）和 $Y$（剪贴板）。你可以进行三种操作： 1. **操作 A**：把一个字符加在字符串 $X$ 的末尾。形式化的，选择一个字符 $c$，然后执行 $X\leftarrow X+c$。执行一次此操作代价为 $A$。 2. **操作 B**：选中所有文本并剪切之。形式化的，执行 $Y\leftarrow X$，然后清空字符串 $X$。执行一次此操作代价为 $B$。 3. **操作 C**：在文本末尾进行一次粘贴。形式化的，执行 $X\leftarrow X+Y$。执行一次此操作代价为 $C$。 给定一个长度为 $N$ 的字符串 $S$ 和 $A,B,C$，你需要求出使得 $X=S$ 的最小代价。

输入一共五行。 第一行一个整数 $N$。 第二行一个字符串 $S$。 第三行至第五行，每行一个整数，分别表示 $A,B,C$，意义如题目描述。

输出一行一个整数，表示最小花费。

【样例解释 #1】 $$ \begin{matrix} \text{序号} & \text{操作} & \text{解释} & X & Y & \text{本步代价} & \text{总代价 }\\ - & - & - & \texttt{""} & \texttt{""} & - & 0\\ 1 & 操作\;A & 在\;X\;末尾加上字符 \;\texttt{'s'} & \texttt{"s"} & \texttt{""} & 10 & 10 \\ 2 & 操作\;B & 全选并剪切 & \texttt{""} & \texttt{"s"} & 5 & 15 \\ 3 & 操作\;C & 粘贴在末尾 & \texttt{"s"} & \texttt{"s"} & 2 & 17 \\ 4 & 操作\;C & 粘贴在末尾 & \texttt{"ss"} & \texttt{"s"} & 2 & 19 \\ 5 & 操作\;A & 在\;X\;末尾加上字符 \texttt{'i'} & \texttt{"ssi"}& \texttt{"s"} & 10 & 29 \\ 6 & 操作\;B & 全选并剪切 & \texttt{""} & \texttt{"ssi"} & 5 & 34 \\ 7 & 操作\;A & 在\;X\;末尾加上字符 \texttt{'m'} & \texttt{"m"} & \texttt{"ssi"} & 44 & 7 \\ 8 & 操作\;C & 在\;X\;末尾加上字符 \texttt{'i'} & \texttt{"mi"} & \texttt{"ssi"} & 54 & 8 \\ 9 & 操作\;C & 粘贴在末尾 & \texttt{"missi"} & \texttt{"ssi"} & 2 & 56 \\ 10 & 操作\;C & 粘贴在末尾 & \texttt{"mississi"} & \texttt{"ssi"} & 2 & 58 \\ 11 & 操作\;C & 在\;X\;末尾加上字符 \texttt{'p'} & \texttt{"mississip"} & \texttt{"ssi"} & 10 & 68 \\ 12 & 操作\;C & 在\;X\;末尾加上字符 \texttt{'p'} & \texttt{"mississipp"} & \texttt{"ssi"} & 10 & 78 \\ 13 & 操作\;C & 在\;X\;末尾加上字符 \texttt{'i'} & \texttt{"mississippi"} & \texttt{"ssi"} & 10 & 88 \\ \end{matrix} $$ 这个样例满足子任务 $3,4,5,6$ 的限制。 【样例解释 #2】 $$ \begin{matrix} \text{序号} & \text{操作} & \text{解释} & X & Y & \text{本步代价} & \text{总代价 }\\ - & - & - & \texttt{""} & \texttt{""} & - & 0\\ 1 & 操作\;A & 在\;X\;末尾加上字符 \;\texttt{'a'} & \texttt{"a"} & \texttt{""} & 1 & 1 \\ 2 & 操作\;A & 在\;X\;末尾加上字符 \;\texttt{'a'} & \texttt{"aa"} & \texttt{""} & 1 & 2 \\ 3 & 操作\;A & 在\;X\;末尾加上字符 \;\texttt{'a'} & \texttt{"aaa"} & \texttt{""} & 1 & 3 \\ 4 & 操作\;A & 在\;X\;末尾加上字符 \;\texttt{'a'} & \texttt{"aaaa"} & \texttt{""} & 1 & 4 \\ 5 & 操作\;B & 全选并剪切 & \texttt{""} & \texttt{"aaaa"} & 1 & 5 \\ 6 & 操作\;C & 粘贴在末尾 & \texttt{"aaaa"} & \texttt{"aaaa"} & 1 & 6 \\ 7 & 操作\;C & 粘贴在末尾 & \texttt{"aaaaaaaa"} & \texttt{"aaaa"} & 1 & 7 \\ 8 & 操作\;C & 粘贴在末尾 & \texttt{"aaaaaaaaaaaa"} & \texttt{"aaaa"} & 1 & 8 \\ 9 & 操作\;C & 粘贴在末尾 & \texttt{"aaaaaaaaaaaaaaaa"} & \texttt{"aaaa"} & 1 & 9 \\ \end{matrix} $$ 这个样例满足子任务 $2,3,4,5,6$ 的限制。 【样例解释 #3】 这个样例满足子任务 $3,4,5,6$ 的限制。 --- 【数据范围】 **本题采用捆绑测试。** 对于 $100\%$ 的数据，$1\le N\le 2500,\;1\le A,B,C\le 10^9,\;|S|=N$。 且保证 $N,A,B,C$ 均为整数，$S$ 仅包含小写字母。 1. 子任务 $1$ （$1$ 分）：$N=3$。 2. 子任务 $2$ （$5$ 分）：$S$ 中只包含字母 $\texttt{'a'}$。 3. 子任务 $3$ （$14$ 分）：$N\le 30$。 4. 子任务 $4$ （$10$ 分）：$N\le 200$。 4. 子任务 $5$ （$32$ 分）：$N\le 10^3$。 5. 子任务 $6$ （$38$ 分）：无附加条件。