P12406 "CZOI-R3" Elimination Sequence.

There are two permutations $a, b$ of length $n$. You can perform the following operations any number of times: - Cyclically shift $a$ left by one position. If $a_1 \neq 0$ before the operation, it costs $x$. - Cyclically shift $a$ right by one position. If $a_1 \neq 0$ before the operation, it costs $y$. - Swap $x$ and $y$. It costs $z$. - If $a_1 = b_1$, cyclically shift $b$ left by one position, and set $a_1 = 0$. This costs nothing. Find the minimum total cost to make $a_i = 0$ for all $1 \le i \le n$. It is guaranteed that the goal can always be achieved by some sequence of operations. $\dag$ : Suppose before a cyclic left shift the sequence is $a_1, a_2, \cdots, a_{n-1}, a_n$, then after the operation it becomes $a_2, \cdots, a_{n-1}, a_n, a_1$. Suppose before a cyclic right shift the sequence is $a_1, a_2, \cdots, a_{n-1}, a_n$, then after the operation it becomes $a_n, a_1, a_2, \cdots, a_{n-1}$.

The first line contains four integers $n, x, y, z$. The second line contains $n$ integers, representing the permutation $a$. The third line contains $n$ integers, representing the permutation $b$.

Output one integer in one line, representing the answer.

**Constraints** **This problem uses bundled testdata.** - Subtask #1 ($10\text{ pts}$): $n \le 10$. - Subtask #2 ($25\text{ pts}$): $x = y = z$. - Subtask #3 ($25\text{ pts}$): $n \le 10^3$. **Depends on Subtask #1.** - Subtask #4 ($40\text{ pts}$): No special properties. **Depends on Subtask #2 #3.** For $100\%$ of the testdata: $1 \le n \le 10^6$, and $a, b$ are permutations of length $n$. $1 \le x, y, z \le 10^6$. Translated by ChatGPT 5