P12756 [POI 2017 R3] 烤三明治 Panini

翻译来自于 [LibreOJ](https://loj.ac/p/5064)。

**题目译自 [XXIV Olimpiada Informatyczna — III etap](https://sio2.mimuw.edu.pl/c/oi24-3/dashboard/) [Zapiekanki](https://szkopul.edu.pl/problemset/problem/w-dbshXVyRol4LIT9jeP-bNn/statement/)** Bajtazar 在拜托尼亚经营一家烤三明治摊位，其产品以卓越的品质和独特的风味闻名遐迩。多年来，他稳固了市场地位，赢得了忠实顾客群。 每天有 $k$ 位顾客光顾，第 $i$ 位在时刻 $t_i$ 到达，每人点一份三明治。Bajtazar 重视顾客体验，恨不得立刻交付订单，但烤箱有限制：一次最多烤 $z$ 份三明治，耗时 $d$，期间无法打开烤箱。他希望顾客的总等待时间最短，可在顾客到达前开始烤制，但必须在顾客到达时烤好——没人爱吃凉三明治。Bajtazar 在时刻 $0$ 到达摊位。 假设 Bajtazar 知晓每位顾客的到达时间，并采用最优烤制策略，顾客的总等待时间是多少？

第一行包含三个正整数 $k, z, d$，分别表示顾客数量、烤箱容量和烤制时间。 第二行包含 $k$ 个整数 $t_1, t_2, \ldots, t_k$ $(0 \leq t_1 \leq t_2 \leq \ldots \leq t_k)$，其中 $t_i$ 表示第 $i$ 位顾客的到达时刻。

输出一行，包含一个整数，表示采用最优烤制策略时，顾客的总等待时间。

**样例 1 解释**  在最优烤制策略中（见图示），Bajtazar 在时刻 $0, 6, 10, 14, 21$ 启动烤箱。首次仅烤一份三明治，之后每次烤两份。烤制时间以灰色表示，顾客等待时间以黑色表示。 **附加样例** 1. $k=z=10, d=1$，所有顾客在时刻 $0$ 到达。 2. $k=2000, z=5, d=200$，顾客到达间隔大于 $d$。 3. $k=3000, z=7, d=1000000$，一半顾客在时刻 $0$ 到达，另一半在时刻 $t_{\frac{k}{2}+i}=i$ 到达。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $z \leq k \leq 200, d \leq 200, t_k \leq 10000$ | $20$ | | $2$ | $z \leq k \leq 200, d, t_k \leq 1000000$ | $30$ | | $3$ | $z \leq k \leq 3000, d, t_k \leq 1000000$ | $50$ |