题目描述

一条道路上从左至右排列着 $m$ 个信号站，初始时从左至右依次编号为 $1,2,\dots,m$，相邻信号站之间相隔 $1$ 单位长度。每个信号站只能往它右侧的任意信号站传输信号（称为普通传递），每单位长度距离需要消耗 $1$ 单位时间。道路的最左侧有一个控制塔，它在最左侧信号站的左侧，与其相隔 $1$ 单位长度。控制塔能与任意信号站进行双向信号传递（称为特殊传递），但每单位长度距离需要消耗 $k$ 个单位时间。对于给定的长度为 $n$ 的信号传递序列 $S$，传递规则如下：

1. 共 $n-1$ 次信号传递，第 $i$ 次信号传递将把信号从 $S_i$ 号信号站传递给 $S_{i+1}$ 号。

2. 若 $S_{i+1}$ 号信号站在 $S_i$ 号右侧，则将使用普通传递方式，从 $S_i$ 号直接传递给 $S_{i+1}$ 号。

3. 若 $S_{i+1}$ 号信号站在 $S_i$ 号左侧，则将使用特殊传递方式，信号将从 $S_i$ 号传递给控制塔，再由控制塔传递给 $S_{i+1}$ 号。

4. 若 $S_i=S_{i+1}$，则信号无须传递。

阿基作为大工程师，他能够任意多次交换任意两个信号站的位置，即他能够重排信号站的顺序，这样会使得 $S$ 消耗的传递时间改变。现在阿基想知道，在他重排信号站顺序后，$S$ 所消耗的传递时间最小能是多少。

输入格式

第一行三个整数 $n,m,k$，分别代表信号传递序列 $S$ 的长度，信号站个数，特殊传递单位长度距离的时间消耗。

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

输出格式

仅一行一个整数表示答案。

3 3 1
1 2 3

2

4 3 1
1 2 3 1

6

提示

【样例解释 $1$】

信号站顺序保持不变，两次使用普通传递方式，时间消耗为 $1+1=2$。

【样例解释 $2$】

对于排列 $1,2,3$，传递时间为 $1+1+(3\times 1+1\times 1)=6$。

对于排列 $1,3,2$，传递时间为 $2+(3\times 1+2\times 1)+(2\times 1+1\times 1)=10$。

对于排列 $2,1,3$，传递时间为 $(2\times 1+1\times 1)+2+(3\times 1+2\times 1)=10$。

对于排列 $2,3,1$，传递时间为 $(3\times 1+1\times 1)+1+1=6$。

对于排列 $3,1,2$，传递时间为 $1+(3\times 1+1\times 1)+1=6$。

对于排列 $3,2,1$，传递时间为 $(3\times 1+2\times 1)+(2\times 1+1\times 1)+2=10$。

【数据范围】

$30\%$ 的数据：$m\leq 8, n\leq 100$。

$60\%$ 的数据：$m\leq 20$。

$70\%$ 的数据：$m\leq 21$。

$80\%$ 的数据：$m\leq 22$。

$100\%$ 的数据：$2\leq m\leq 23$，$2\leq n\leq 10^5$，$1\leq k\leq 100$，$1\leq S_i\leq m$。