#3302. 「联合省选 2020 A | B」信号传递

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

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

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\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

见附加文件中 transfer3.intransfer3.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