题目描述
有两个长为 n 的排列 a,b,你可以做任意次操作:
- 将 a 循环左移一位。若在进行操作前 a1=0,则消耗 x 点代价。
- 将 a 循环右移一位。若在进行操作前 a1=0,则消耗 y 点代价。
- 交换 x,y。消耗 z 点代价。
- 若 a1=b1,将 b 循环左移一位,同时令 a1=0。不消耗代价。
求出让对于 ∀1≤i≤n 有 ai=0 的最小代价,显然一定可以通过若干次操作达成目标。
†:设某次循环左移操作前序列为 a1,a2,⋯,an−1,an,则操作后序列为 a2,⋯,an−1,an,a1。设某次循环右移操作前序列为 a1,a2,⋯,an−1,an,则操作后序列为 an,a1,a2,⋯,an−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 pts):n≤10。
- Subtask #2(25 pts): x=y=z。
- Subtask #3(25 pts):n≤103。依赖 Subtask #1。
- Subtask #4(40 pts):无特殊性质。依赖 Subtask #2 #3。
对于 100% 的数据,1≤n≤106,a,b 为长度为 n 的排列。1≤x,y,z≤106。