#5064. 「POI2017 R3」烤三明治 Panini

传统
时间限制：1000 - 2000 ms
内存限制：256 MiB

题目描述

题目译自 XXIV Olimpiada Informatyczna — III etap Zapiekanki

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$ 位顾客的到达时刻。

输出格式

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

样例

输入

9 2 4
3 7 10 12 12 13 13 24 25

输出

19

在最优烤制策略中（见图示），Bajtazar 在时刻 $0$, $6$, $10$, $14$, $21$ 启动烤箱。首次仅烤一份三明治，之后每次烤两份。烤制时间以灰色表示，顾客等待时间以黑色表示。

附加样例

• $k=z=10$, $d=1$，所有顾客在时刻 $0$ 到达。
• $k=2000$, $z=5$, $d=200$，顾客到达间隔大于 $d$。
• $k=3000$, $z=7$, $d=1000000$，一半顾客在时刻 $0$ 到达，另一半在时刻 $t_{\frac{k}{2}+i}=i$ 到达。

数据范围与提示

详细子任务附加限制及分值如下表所示。