P11793 [JOI 2016 Final] 橙子装箱 / Oranges

CXR 决定将收获的 $n$ 个橙子分装进一些箱子内。在 NXY 的工厂中，橙子排列在输送带上，依次编号为 $1\dots n$。橙子 $i(1\leq i\leq n)$ 的大小为 $A_i$。由于分拣不方便，同一个箱子内，橙子的编号必须连续。 一个箱子内最多可以装 $m$ 个橙子。在一个箱子内装一些橙子的成本为 $k+s\times (a-b)$。$k$ 是箱子本身的成本，所有箱子的成本一样。$s$ 是该箱子中橙子的数目。 $a$ 是该箱子中最大橙子的大小，$b$ 是该箱子中最小橙子的大小。 求包装这 $n$ 个橙子所需的最小成本。

第一行有三个整数 $n,m,k$，用空格分隔。 在接下来的 $n$ 行中，第 $i$ 行 $(1\leq i\leq n)$ 有一个整数 $A_i$。

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

【数据范围与约定】 - $1\le N\le 2\times 10^4$。 - $1\le M\le 10^3$。 - $0\le K\le 10^9$。 - $1\le A_i\le 10^9 (1\le i\le N)$。 - $M\le N$。 1. Subtask $1$（$20$ pts）：$N\le 20$。 2. Subtask $2$（$50$ pts）：$N \le 2000,M \le 100$。 3. Subtask $3$（$30$ pts）：无特殊限制。