Problem Description

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}$.

Input Format

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 Format

Output one integer in one line, representing the answer.

2 1 1 1
1 2
2 1

1

5 4 3 2
1 4 3 2 5
5 1 4 2 3

3

Hint

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