Mr. Panda recently got a brand-new typewriter as a birthday gift from Mr. Champion. Mr. Panda likes the typewriter so much. He wants to use it to type a thank you letter $S$ and mail it to Mr. Champion.
To type the thank you letter, Mr. Panda starts with an empty string on a white-paper, and the following operations are allowed to perform by using the typewriter:
Mr. Panda needs to make his string exactly the same as the contents in the thank you letter $S$. Note that Mr. Panda must create exactly the thank you letter with no additional character.
Mr. Panda wants to find a way to type the thank you letter with the minimum amount of spent time. Because Mr. Panda is too lazy, he asks for your help.
Could you please help Mr. Panda find an optimized way to type the thank you letter so that the amount of time spent is minimized? Note that you just need to tell Mr. Panda the minimum number of time units that are needed.
The first line of the input gives the number of test cases $T$ ($1 <= T <= 100$). $T$ test cases follow.
Each test case starts with a line consisting of four integers $n$ ($1 <= n <= 5000$), the length of Mr. Panda's thank you letter, $X$, $Y$ and $Z$ ($1 <= X, Y, Z <= 10^9$). $X$, $Y$ and $Z$ are the time cost of operations that can be performed by the typewriter.
Then, a line consisting of $n$ integers $S_0$, $S_1$, $\\dots$, $S_{n -1}$ follows, denoting the contents of Mr. Panda's thank you letter. Each integer $S_i$ ($1 <= S_i <= 10^9$) represents a single character in the letter.
It is guaranteed that $n <= 1000$ in at least 80% of test cases.
For each test case, output one line containing "_Case #x: y_", where _x_ is the test case number (starting from $1$) and _y_ is the minimum number of time units that are needed to type the thank you letter.
## Input
The first line of the input gives the number of test cases $T$ ($1 <= T <= 100$). $T$ test cases follow.Each test case starts with a line consisting of four integers $n$ ($1 <= n <= 5000$), the length of Mr. Panda's thank you letter, $X$, $Y$ and $Z$ ($1 <= X, Y, Z <= 10^9$). $X$, $Y$ and $Z$ are the time cost of operations that can be performed by the typewriter.Then, a line consisting of $n$ integers $S_0$, $S_1$, $\\dots$, $S_{n -1}$ follows, denoting the contents of Mr. Panda's thank you letter. Each integer $S_i$ ($1 <= S_i <= 10^9$) represents a single character in the letter.It is guaranteed that $n <= 1000$ in at least 80% of test cases.
## Output
For each test case, output one line containing "_Case #x: y_", where _x_ is the test case number (starting from $1$) and _y_ is the minimum number of time units that are needed to type the thank you letter.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- Let $ n_k \in \mathbb{Z} $ be the length of the target string.
- Let $ X_k, Y_k, Z_k \in \mathbb{Z}^+ $ be the time costs for:
- $ X_k $: appending a single character,
- $ Y_k $: deleting the last character,
- $ Z_k $: copying the current string and appending it to itself (doubling).
- Let $ S_k = (s_{k,0}, s_{k,1}, \dots, s_{k,n_k-1}) $ be the target sequence of characters (integers representing distinct symbols).
**Constraints**
1. $ 1 \le T \le 100 $
2. $ 1 \le n_k \le 5000 $
3. $ 1 \le X_k, Y_k, Z_k \le 10^9 $
4. $ 1 \le s_{k,i} \le 10^9 $ for all $ i \in \{0, \dots, n_k-1\} $
5. In at least 80% of cases: $ n_k \le 1000 $
**Objective**
For each test case $ k $, compute the minimum total time to construct $ S_k $ starting from an empty string, using only the following operations:
- Append $ s_{k,i} $ at the end: cost $ X_k $,
- Delete the last character: cost $ Y_k $,
- Copy the entire current string and append it to itself: cost $ Z_k $.
Let $ dp[i] $ denote the minimum cost to construct the prefix $ s_{k,0}s_{k,1}\dots s_{k,i-1} $.
We seek $ dp[n_k] $.
Transition:
- $ dp[0] = 0 $
- For $ i \ge 1 $:
$$
dp[i] = \min \left(
\begin{array}{c}
dp[i-1] + X_k, \\
dp[i+1] + Y_k \quad \text{(if } i < n_k \text{, for backward propagation)}, \\
\min_{\substack{j < i \\ j \text{ even}, \\ s_{k,j/2 : j} = s_{k,j : j + j/2}}} \left\{ dp[j/2] + Z_k \right\} \quad \text{for } j = i/2 \text{ and } i \text{ even}
\end{array}
\right)
$$
(Note: The doubling operation is only valid if the first half of the current string equals the second half.)
**Simplified Objective**
Minimize total time to build $ S_k $ using append ($X$), delete ($Y$), and double ($Z$) operations.