F. Frodo and Sam
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Frodo and Sam, the great hobbits of Middle-earth, are on an adventure to destroy the One Ring. Their journey takes them to the treacherous Mines of Moria, where a Balrog — one of Morgoth's most feared creatures — dwells.

As they descend into the depths of Moria, something extraordinary happens — this is where the plot twists! The Balrog awakens and casts a powerful spell on Frodo and Sam, transporting them to another plane of reality.

Frodo and Sam are taken to the top of a mountain, where there are two paths made of magical rocks. Frodo stands to the left of these paths, and Sam to the right. The paths can be represented by two permutations $$$P$$$ and $$$Q$$$ of length $$$N$$$, where the type of the $$$i$$$-th rock from left to right is $$$P_i$$$ on the first path and $$$Q_i$$$ on the second.

To escape this illusory world and continue their journey to Mordor, Frodo and Sam must destroy some of these rocks so that the two permutations $$$P$$$ and $$$Q$$$ of rock types become identical, but they cannot destroy all the rocks on both paths.

Frodo and Sam begin destroying the rocks simultaneously. For each of the two paths, Frodo may destroy as many rocks as he wants starting from the left side of both paths, and Sam can do the same starting from the right. More formally, Frodo will choose two integers $$$(a, b)$$$ and destroy the rocks $$$P_1, P_2, \cdots, P_a$$$ and $$$Q_1, Q_2, \cdots, Q_b$$$, while Sam will choose two integers $$$(c, d)$$$ and destroy the rocks $$$P_N, P_{N-1}, \cdots, P_c$$$ and $$$Q_N, Q_{N-1}, \cdots, Q_d$$$. Note that Frodo and/or Sam may choose not to destroy any rocks.

Given that Frodo takes $$$F$$$ time to destroy a rock, Sam takes $$$S$$$ time to destroy a rock, and the time to move between any two rocks is zero, what is the minimum time they need to spend destroying rocks to escape the Balrog's magical realm?

Input

The first line of input consists of three integers $$$N$$$ $$$(1 \le N \le 10^5)$$$, $$$F$$$, and $$$S$$$ $$$(1 \le F, S \le 10^9)$$$ — the number of rocks separating Frodo and Sam, the time Frodo takes to destroy a rock, and the time Sam takes to destroy a rock, respectively.

The second line contains a permutation of $$$N$$$ integers $$$P_1, P_2, \cdots, P_N$$$ $$$(1 \le P_i \le N)$$$ where $$$P_i$$$ represents the type of the $$$i$$$-th rock on the first path from left to right.

The third line contains a permutation of $$$N$$$ integers $$$Q_1, Q_2, \cdots, Q_N$$$ $$$(1 \le Q_i \le N)$$$ where $$$Q_i$$$ represents the type of the $$$i$$$-th rock on the second path from left to right.

Output

The output should contain a single integer — the answer to the problem.

Examples
Input
3 1 2
1 2 3
3 1 2
Output
2
Input
1 1 2
1
1
Output
0
Input
8 24 16
7 4 8 1 2 3 6 5
3 2 7 4 5 8 1 6
Output
144
Input
7 9 6
7 5 1 6 2 3 4
3 2 5 1 6 4 7
Output
30
Note

In the third case, Frodo and Sam can remove rocks so that $$$P = [2]$$$ and $$$Q = [2]$$$. Thus, Frodo must destroy $$$5$$$ rocks in total, taking $$$120$$$ units of time, and Sam must destroy $$$9$$$ rocks in total, taking $$$144$$$ units of time.

In the fourth case, Frodo and Sam can remove rocks so that $$$P = [5, 1, 6]$$$ and $$$Q = [5, 1, 6]$$$. Thus, Frodo must destroy $$$3$$$ rocks in total, taking $$$27$$$ units of time, and Sam must destroy $$$5$$$ rocks in total, taking $$$30$$$ units of time.