Score : $550$ points

问题陈述

KEYENCE 以快速交货而闻名。

在这个问题中，日历按照第 $1$ 天，第 $2$ 天，第 $3$ 天，$\dots$ 进行。

有订单 $1,2,\dots,N$，并且已知订单 $i$ 将在第 $T_i$ 天下单。 对于这些订单，根据以下规则进行发货。

• 最多可以一起发货 $K$ 个订单。
• 订单 $i$ 只能在第 $T_i$ 天或之后发货。
• 一旦发货，必须等待 $X$ 天后才能进行下一次发货。
  • 也就是说，如果在第 $a$ 天发货，下一次发货可以在第 $a+X$ 天进行。

从订单下单到发货的每一天，不满情绪会累积增加 $1$。 也就是说，如果订单 $i$ 在第 $S_i$ 天发货，那么该订单累积的不满情绪是 $(S_i - T_i)$。

当你最优地安排发货日期时，找出所有订单累积的最小可能总不满情绪。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

KEYENCE is famous for quick delivery.

In this problem, the calendar proceeds as Day $1$, Day $2$, Day $3$, $\dots$.

There are orders $1,2,\dots,N$, and it is known that order $i$ will be placed on Day $T_i$.
For these orders, shipping is carried out according to the following rules.

• At most $K$ orders can be shipped together.
• Order $i$ can only be shipped on Day $T_i$ or later.
• Once a shipment is made, the next shipment cannot be made until $X$ days later.
  • That is, if a shipment is made on Day $a$, the next shipment can be made on Day $a+X$.

For each day that passes from order placement to shipping, dissatisfaction accumulates by $1$ per day.
That is, if order $i$ is shipped on Day $S_i$, the dissatisfaction accumulated for that order is $(S_i - T_i)$.

Find the minimum possible total dissatisfaction accumulated over all orders when you optimally schedule the shipping dates.

Constraints

• All input values are integers.
• $1 \le K \le N \le 100$
• $1 \le X \le 10^9$
• $1 \le T_1 \le T_2 \le \dots \le T_N \le 10^{12}$

Input

The input is given from Standard Input in the following format:

$N$ $K$ $X$

$T_1$ $T_2$ $\dots$ $T_N$

Output

Print the answer as an integer.

Sample Input 1

5 2 3
1 5 6 10 12

Sample Output 1

2

For example, by scheduling shipments as follows, we can achieve a total dissatisfaction of $2$, which is the minimum possible.

• Ship order $1$ on Day $1$.
  • This results in dissatisfaction of $(1-1) = 0$, and the next shipment can be made on Day $4$.
• Ship orders $2$ and $3$ on Day $6$.
  • This results in dissatisfaction of $(6-5) + (6-6) = 1$, and the next shipment can be made on Day $9$.
• Ship order $4$ on Day $10$.
  • This results in dissatisfaction of $(10-10) = 0$, and the next shipment can be made on Day $13$.
• Ship order $5$ on Day $13$.
  • This results in dissatisfaction of $(13-12) = 1$, and the next shipment can be made on Day $16$.

Sample Input 2

1 1 1000000000
1000000000000

Sample Output 2

0

Sample Input 3

15 4 5
1 3 3 6 6 6 10 10 10 10 15 15 15 15 15

Sample Output 3

35