103745: [Atcoder]ABC374 F - Shipping

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

问题陈述

KEYENCE 以快速交货而闻名。

在这个问题中，日历按天顺次进行，即第1天，第2天，第3天，……。

有订单1,2,……,N，已知订单i将在第T_i天下单。
对于这些订单，运输按照以下规则进行。

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

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

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

约束条件

• 所有输入值都是整数。
• 1 ≤ K ≤ N ≤ 100
• 1 ≤ X ≤ 10^9
• 1 ≤ T_1 ≤ T_2 ≤ …… ≤ T_N ≤ 10^{12}

输入

输入从标准输入以下格式给出：

N K X
T_1 T_2 …… T_N

输出

以整数形式打印答案。

示例输入1

5 2 3
1 5 6 10 12

示例输出1

2

例如，通过以下方式安排发货，我们可以实现总不满情绪为2，这是可能的最小值。

• 在第1天发货订单1。
  • 这导致的不满情绪为(1-1) = 0，下一次发货可以在第4天。
• 在第6天发货订单2和3。
  • 这导致的不满情绪为(6-5) + (6-6) = 1，下一次发货可以在第9天。
• 在第10天发货订单4。
  • 这导致的不满情绪为(10-10) = 0，下一次发货可以在第13天。
• 在第13天发货订单5。
  • 这导致的不满情绪为(13-12) = 1，下一次发货可以在第16天。

示例输入2

1 1 1000000000
1000000000000

示例输出2

0

示例输入3

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

示例输出3

35