题目描述

有两个长为 $n$ 的排列 $a,b$，你可以做任意次操作：

• 将 $a$ 循环左移一位。若在进行操作前 $a_1\neq 0$，则消耗 $x$ 点代价。
• 将 $a$ 循环右移一位。若在进行操作前 $a_1\neq 0$，则消耗 $y$ 点代价。
• 交换 $x,y$。消耗 $z$ 点代价。
• 若 $a_1=b_1$，将 $b$ 循环左移一位，同时令 $a_1=0$。不消耗代价。

求出让对于 $\forall 1\le i\le n$ 有 $a_i=0$ 的最小代价，显然一定可以通过若干次操作达成目标。

$\dag$：设某次循环左移操作前序列为 $a_1,a_2,\cdots,a_{n-1},a_n$，则操作后序列为 $a_2,\cdots,a_{n-1},a_n,a_1$。设某次循环右移操作前序列为 $a_1,a_2,\cdots,a_{n-1},a_n$，则操作后序列为 $a_n,a_1,a_2,\cdots,a_{n-1}$。

输入格式

第一行输入四个整数 $n,x,y,z$。

第二行输入 $n$ 个整数，表示排列 $a$。

第三行输入 $n$ 个整数，表示排列 $b$。

输出格式

一行输出一个整数，表示答案。

2 1 1 1
1 2
2 1

1

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

3

提示

【数据范围】

本题采用捆绑测试。

• 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$。依赖 Subtask #1。
• Subtask #4（$40\text{ pts}$）：无特殊性质。依赖 Subtask #2 #3。

对于 $100\%$ 的数据，$1\le n\le 10^6$，$a,b$ 为长度为 $n$ 的排列。$1\le x,y,z\le 10^6$。