P12406 「CZOI-R3」消除序列

有两个长为 $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}$。

无

无

**【数据范围】** **本题采用捆绑测试。** - 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$。