Byteasar 经营着一家世界闻名的帕尼尼店，以其产品的质量和独特的风味而闻名。多年来，他获得了稳定的市场地位和一批忠实的顾客。

每天有 $k$ 位顾客来到他的店里，第 $i$ 位顾客在时间 $t_i$ 到达。每位顾客点一个帕尼尼。Byteasar 很想立即为每位忠实的顾客提供服务，但不幸的是，这无法做到：他一次最多只能烤 $z$ 个帕尼尼，且烘烤过程需要恰好 $d$ 个单位时间。不用说，烘烤过程不能以任何方式暂停、停止或干扰（例如添加或移除帕尼尼），因为这会破坏其绝佳的口感。因此，Byteasar 决定最小化顾客的总服务时间，即他们等待订单的总时间。Byteasar 非常了解他的顾客，以至于他知道他们的到达时间和喜爱的帕尼尼，因此他可以在顾客到达之前就开始烘烤。然而，任何顾客的订单都不能在他们到达之前准备好，因为没有人喜欢吃冷的帕尼尼！Byteasar 在时间 $0$ 到达他的店。

顾客的最小总服务/等待时间是多少？

输入格式

标准输入的第一行包含三个正整数 $k, z$ 和 $d$，分别指定了顾客数量、烤箱容量和烘烤时长。第二行包含一个由 $k$ 个整数组成的序列 $t_1, t_2, \dots, t_k$ ($0 \le t_1 \le t_2 \le \dots \le t_k$)；数字 $t_i$ 是第 $i$ 位顾客的到达时间。

输出格式

输出一个整数，即在最优烘烤计划下顾客的总服务/等待时间。

样例

输入格式 1

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

输出格式 1

19

说明

在最优烘烤计划中（如图所示），Byteasar 分别在时间 $0, 6, 10, 14$ 和 $21$ 开始烘烤。第一次他只烤了一个帕尼尼，此后每次都烤两个。烘烤时间用灰色标记，等待时间用黑色标记。

样例评分测试

• 1ocen: $k = z = 10, d = 1$，所有顾客都在时间 $0$ 到达；
• 2ocen: $k = 2000, z = 5, d = 200$，顾客到达的时间间隔至少为 $d$ 个单位时间；
• 3ocen: $k = 3000, z = 7, d = 1\,000\,000$，一半顾客在时间 $0$ 到达，另一半顾客在时间 $t_{\frac{k}{2}+i} = i$ 到达。

子任务

测试集由以下子任务组成。在每个子任务内，可能包含多个测试组。