题目描述

小z 决定将刚收获的 $n$ 个苹果分装进一些箱子中。 这些苹果排列在输送带上，依次编号为 $1,2,3,...,n$。 第 $i$ 个苹果的大小为 $a_i$，由于分拣不方便，所以要求同一个箱子内的苹果编号必须连续。

每个箱子最多可以装 $m$ 个苹果。

在一个箱子内装入若干苹果的成本为： $cost=k+cnt*(x-y)$。

其中：

• $k$ 为箱子本身的固定成本；
• $cnt$ 为该箱子中苹果的数量；
• $x$ 为该箱子中最大的苹果大小；
• $y$ 为该箱子中最小的苹果大小。

请你计算，将这 $n$ 个苹果全部打包所需的最小总成本

数据范围:

对于 $60$%的数据： $1≤n≤20,1≤m≤20,1≤k,a_i≤100$。

对于 $100$%的数据： $1≤n≤10^4,1≤m≤10^3,1≤k,a_i≤10^9$。

输入格式

第一行有三个整数 $n,m,k$。

第二行有 $n$ 个整数 $a_1,a_2,...,a_n$。

输出格式

输出一个整数，表示包装这 $n$ 个苹果所需的最小成本。

5 3 30
100 10 15 75 80

110

5 3 10
100 10 15 75 80

50

提示

样例数据1解释：

$([100],[10,15],[75,80])$ 的总成本最小，为 ​$110$​。