EOJ-自适应编程学习平台

🐢🐢 决定将收获的 $n$ 个橙子分装进一些箱子内。在 👻👻 的工厂中，橙子排列在输送带上，依次编号为 $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$（$33$ pts）：$N\le 20$。
2. Subtask $2$（$33$ pts）：$N \le 2000,M \le 100$。
3. Subtask $3$（$33$ pts）：无特殊限制。