题目描述

flow 有一个长度为 $n$ 的整数序列 $\{a\}$，和一个常数 $k$。

flow 想要简化这个序列使得其只剩下恰好一个数，他可以进行 $n-1$ 次以下两种操作：

1. 花费 $x$ 的代价，选择 $1\le i<n$，记 $s=(a_i+a_{i+1}) \bmod k$，将 $a_i\gets s$，删去 $a_{i+1}$。
2. 花费 $y$ 的代价，选择 $1\le i\le n$，满足 $a_i=0$，删去 $a_i$。

操作后令 $n\gets n-1$。

flow 想要让最终代价 $cost$ 最小。请你找出这个值。

本题的 $\{a\}$ 生成方式较为特殊，具体参见数据范围。

输入格式

第一行四个整数 $n,k,x,y$。

第二行 $n$ 个整数，表示 $a_i$。

输出格式

一行一个正整数 $cost$。

7 40 2 1
10 20 30 0 30 20 10

10

提示

样例 1 解释

一种可能的方案为：

1. 使用操作 $2$，选择位置 $4$，序列变为 $\{10,20,30,30,20,10\}$，总花费为 $1$。
2. 使用操作 $1$，选择位置 $2$，序列变为 $\{10,10,30,20,10\}$，总花费为 $3$。
3. 使用操作 $1$，选择位置 $2$，序列变为 $\{10,0,20,10\}$，总花费为 $5$。
4. 使用操作 $2$，选择位置 $2$，序列变为 $\{10,20,10\}$，总花费为 $6$。
5. 使用操作 $1$，选择位置 $1$，序列变为 $\{30,10\}$，总花费为 $8$。
6. 使用操作 $1$，选择位置 $1$，序列变为 $\{0\}$，总花费为 $10$。

可以证明，$cost_{\min}=10$。

数据范围

本题采用捆绑测试。

对于 $100\%$ 的数据，$1\le n\le6000$，$2\le k \le 10^4$，$0\le a_i<k$，$1\le x,y \le 10^5$，保证 $a_i$ 在 $[0,k)$ 内独立均匀随机生成。

• Subtask1(10pts)：$n\le10$。
• Subtask2(15pts)：$n,k\le80$。
• Subtask3(25pts)：$n\le500$。
• Subtask4(10pts)：$k\ge 9000$。
• Subtask5(40pts)：$k\ge400$。