UOJ Logo Universal Online Judge

UOJ

#542. 【统一省选2020】信号传递

附件下载 统计

一条道路上从左至右排列着 $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$。

输出格式

一行一个整数表示答案。

样例1

input

3 3 1
1 2 3

output

2

explanation

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

样例2

input

4 3 1
1 2 3 1

output

6

explanation

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

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

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

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

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

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

样例3

见附加文件中 ex_transfer3.inex_transfer3.ans

数据范围

对于前 $30\%$ 的数据:$m\le 8, n\le 100$。

对于前 $60\%$ 的数据:$m\le 20$。

对于前 $70\%$ 的数据:$m\le 21$。

对于前 $80\%$ 的数据:$m\le 22$。

对于 $100\%$ 的数据:$2\le m\le23, 2\le n\le 10^5, 1\le k\le 100,1\le S_i\le m$。

时间限制: $2\texttt{s}$

空间限制: $512\texttt{MB}$

附加文件