题目描述
Problem Background
JOISC2022 D2T1
Problem Description
JOI Corporation is a company renowned for its "useless inventions." Recently, JOI Corporation developed a new editor called "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, both initially empty:
- Operation A: Input character $c$, updating $X$ to $X + c$.
- Operation B: Select all characters and cut them, updating $Y$ to $X$ and setting $X$ to an empty string.
- Operation C: Paste the clipboard's string to the end of the current string, updating $X$ to $X + Y$.
For strings or characters $x$ and $y$, $x + y$ denotes the concatenation of $x$ and $y$. Each operation A, B, and C costs $A$, $B$, and $C$ units of time, respectively.
You have installed the "Useless Editor" and want to input a string $S$ of length $N$ as quickly as possible.
You need to calculate the minimum time required to input the string $S$.
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 input.
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 a single integer, the minimum time required to input the string $S$.
Sample Input and Output
Sample Input #1
11
mississippi
10
5
2
Sample Output #1
88
Sample Input #2
16
aaaaaaaaaaaaaaaa
1
1
1
Sample Output #2
9
Sample Input #3
18
aababbbababbbaabbb
1000000000
100000
10000000
Sample Output #3
8060200000
Notes/Hints
Sample Explanation #1
The following is an optimal sequence of operations:
| Round | Operation | Explanation | $X$ | $Y$ | Cost | Total Time |
|---|---|---|---|---|---|---|
| - | - | - | "" |
"" |
- | $0$ |
| $1$ | Operation A | Input character | "s" |
"" |
$10$ | $10$ |
| $2$ | Operation B | Select and cut | "" |
"s" |
$5$ | $15$ |
| $3$ | Operation C | Paste at end | "s" |
"s" |
$2$ | $17$ |
| $4$ | Operation C | Paste at end | "ss" |
"s" |
$2$ | $19$ |
| $5$ | Operation A | Input character | "ssi" |
"s" |
$10$ | $29$ |
| $6$ | Operation B | Select and cut | "" |
"ssi" |
$5$ | $34$ |
| $7$ | Operation A | Input character | "m" |
"ssi" |
$10$ | $44$ |
| $8$ | Operation A | Input character | "mi" |
"ssi" |
$10$ | $54$ |
| $9$ | Operation C | Paste at end | "missi" |
"ssi" |
$2$ | $56$ |
| $10$ | Operation C | Paste at end | "mississi" |
"ssi" |
$2$ | $58$ |
| $11$ | Operation A | Input character | "mississip" |
"ssi" |
$10$ | $68$ |
| $12$ | Operation A | Input character | "mississipp" |
"ssi" |
$10$ | $78$ |
| $13$ | Operation A | Input character | "mississippi" |
"ssi" |
$10$ | $88$ |
This sample satisfies the constraints of subtasks $3, 4, 5, 6$.
Sample Explanation #2
An optimal strategy is as follows:
| Round | Operation | Explanation | $X$ | $Y$ | Cost | Total Time |
|---|---|---|---|---|---|---|
| - | - | - | "" |
"" |
- | $0$ |
| $1$ | Operation A | Input character | "a" |
"" |
$1$ | $1$ |
| $2$ | Operation A | Input character | "aa" |
"" |
$1$ | $2$ |
| $3$ | Operation A | Input character | "aaa" |
"" |
$1$ | $3$ |
| $4$ | Operation A | Input character | "aaaa" |
"" |
$1$ | $4$ |
| $5$ | Operation B | Select and cut | "" |
"aaaa" |
$1$ | $5$ |
| $6$ | Operation C | Paste at end | "aaaa" |
"aaaa" |
$1$ | $6$ |
| $7$ | Operation C | Paste at end | "aaaaaaaa" |
"aaaa" |
$1$ | $7$ |
| $8$ | Operation C | Paste at end | "aaaaaaaaaaaa" |
"aaaa" |
$1$ | $8$ |
| $9$ | Operation C | Paste at end | "aaaaaaaaaaaaaaaa" |
"aaaa" |
$1$ | $9$ |
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$.
Data Range
For all data, the following constraints apply:
- $1 \leq N \leq 2500$
- $S$ is a string of length $N$ consisting of lowercase letters.
- $1 \leq A, B, C \leq 10^9$
Detailed subtask constraints and scores are as follows:
| Subtask Number | Additional Constraints | Score |
|---|---|---|
| $1$ | $N = 3$ | $1$ |
| $2$ | $S$ consists only of the character a |
$5$ |
| $3$ | $N \leq 30$ | $14$ |
| $4$ | $N \leq 200$ | $10$ |
| $5$ | $N \leq 1000$ | $32$ |
| $6$ | No additional constraints | $38$ |
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分