题目描述

有 $N$ 个订单，编号为 $1,2,⋅⋅⋅,N$。订单 $i$ 将在第 $T_i$ 天下达。

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

• 最多有 $K$ 个订单可以一起发货。
• 订单 $i$ 只能在第 $T_i$ 天或之后发货。
• 一旦发货，下一次发货要等到 $X$ 天之后。也就是说，如果在 $a$ 日发货，下一批货物只能在 $a+X$ 日及以后发货。

从下单到发货，每过一天，不满意度就会每天累积 $1$。也就是说，如果订单 $i$ 在第 $S_i$ 天发货，则该订单的不满意度累积为 $(S_i−T_i)$。

求优化安排发货日期后，所有订单累积的不满意度总和的最小值。

输入格式

第一行包含三个整数 $N$、$K$ 和 $X$。

第二行包含 $N$ 个整数 $T_1,T_2,⋅⋅⋅,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 ≤ K ≤ N ≤ 100, 1 ≤ X ≤ 10^9, 1 ≤ T_1 ≤ T_2 ≤ · · · ≤ T_N ≤ 10^{12}$。