发货

题目描述

KEYENCE 以快速配送著称。

在本题中，日历按第 1 天、第 2 天、第 3 天、$\dots$ 推进。

有 $1, 2, \dots, N$ 共 $N$ 个订单，已知订单 $i$ 会在第 $T_i$ 天被下单。

对于这些订单，按以下规则进行发货：

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

从下单到发货每经过一天，不满值增加 $1$。

即，如果订单 $i$ 在第 $S_i$ 天发货，则该订单累积的不满值为 $(S_i - T_i)$。

请在最优地安排发货日期时，求所有订单累积的不满值总和的最小值。

输入格式

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

$N$ $K$ $X$
$T_1$ $T_2$ $\dots$ $T_N$

输出格式

以整数输出答案。

样例

5 2 3
1 5 6 10 12

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 天发货。

1 1 1000000000
1000000000000

0

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

35

数据范围

• 所有输入均为整数
• $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}$