Background

JOISC2022 D2T1

Problem Description

JOI Company is a company famous for “useless inventions”. Recently, JOI Company developed an editor called the “Useless Editor”.

In this editor, you can perform the following operations to input a string. Let $X$ be the string on the screen and $Y$ be the string in the clipboard. Initially, both are empty strings:

• Operation A: Input a character $c$, i.e. update $X$ to $X+c$.
• Operation B: Select all characters and cut, i.e. update $Y$ to $X$, and set $X$ to the empty string.
• Operation C: Paste the string in the clipboard to the end of the current string, i.e. update $X$ to $X+Y$.

For strings or characters $x,y$, $x+y$ means the result of concatenating $x$ and $y$ in order. Performing one operation A, B, C costs $A,B,C$ units of time respectively.

You installed the “Useless Editor” and want to input a string $S$ of length $N$ as fast as possible.

You need to compute the minimum total time required.

Input Format

The first line contains an integer $N$, the length of the string.

The second line contains a string $S$ of length $N$, the string to be typed.

The third line contains an integer $A$, the cost of operation A.

The fourth line contains an integer $B$, the cost of operation B.

The fifth line contains an integer $C$, the cost of operation C.

Output Format

Output one integer in one line, the minimum number of time units required to input the string $S$.

11
mississippi
10
5
2

88

16
aaaaaaaaaaaaaaaa
1
1
1

9

18
aababbbababbbaabbb
1000000000
100000
10000000

8060200000

Hint

[Sample Explanation #1]

One optimal sequence of operations is as follows:

This sample satisfies the constraints of subtasks $3,4,5,6$.

[Sample Explanation #2]

One optimal strategy is as follows:

This sample satisfies the constraints of subtasks $2,3,4,5,6$.

[Sample Explanation #3]

This sample satisfies the constraints of subtasks $3,4,5,6$.

[Constraints]

For all testdata, it holds that:

• $1\leq N\leq 2500$.
• $S$ is a lowercase letter string of length $N$.
• $1\leq A,B,C\leq 10^9$.

The additional constraints and scores for each subtask are shown in the table below:

Translated by ChatGPT 5