一条道路上从左至右排列着 m 个信号站,初始时从左至右依次编号为 1,2,…,m,相邻信号站之间相隔 1 单位长度。每个信号站只能往它右侧的任意信号站传输信号(称为普通传递),每单位长度距离需要消耗 1 单位时间。道路的最左侧有一个控制塔,它在最左侧信号站的左侧,与其相隔 1 单位长度。控制塔能与任意信号站进行双向信号传递(称为特殊传递),但每单位长度距离需要消耗 k 个单位时间。对于给定的长度为 n 的信号传递序列 S,传递规则如下:
- 共 n−1 次信号传递,第 i 次信号传递将把信号从 Si 号信号站传递给 Si+1 号。
- 若 Si+1 号信号站在 Si 号右侧,则将使用普通传递方式,从 Si 号直接传递给 Si+1 号。
- 若 Si+1 号信号站在 Si 号左侧,则将使用特殊传递方式,信号将从 Si 号传递给控制塔,再由控制塔传递给 Si+1 号。
- 若 Si=Si+1,则信号无须传递。
阿基作为大工程师,他能够任意多次交换任意两个信号站的位置,即他能够重排信号站的顺序,这样会使得 S 消耗的传递时间改变。现在阿基想知道,在他重排信号站顺序后,S 所消耗的传递时间最小能是多少。
输入格式
第一行三个整数 n,m,k,分别代表信号传递序列 S 的长度,信号站个数,特殊传递单位长度距离的时间消耗。
第二行 n 个整数,第 i 个整数表示 Si。
输出格式
仅一行一个整数表示答案。
样例数据
样例 1 输入
3 3 1
1 2 3
样例 1 输出
2
样例 1 解释
信号站顺序保持不变,两次使用普通传递方式,时间消耗为 1+1=2。
样例 2 输入
4 3 1
1 2 3 1
样例 2 输出
6
样例 2 解释
对于排列 1,2,3,传递时间为 1+1+(3×1+1×1)=6。
对于排列 1,3,2,传递时间为 2+(3×1+2×1)+(2×1+1×1)=10。
对于排列 2,1,3,传递时间为 (2×1+1×1)+2+(3×1+2×1)=10。
对于排列 2,3,1,传递时间为 (3×1+1×1)+1+1=6。
对于排列 3,1,2,传递时间为 1+(3×1+1×1)+1=6。
对于排列 3,2,1,传递时间为 (3×1+2×1)+(2×1+1×1)+2=10。
样例 3
见下发文件。
子任务
30% 的数据:m≤8,n≤100。
60% 的数据:m≤20。
70% 的数据:m≤21。
80% 的数据:m≤22。
100% 的数据:2≤m≤23,2≤n≤105,1≤k≤100,1≤Si≤m。