[ABC374] F - Shipping

F - Shipping

Time Limit: 5 sec / Memory Limit: 1024 MB

分数: 550 分

题面

KEYENCE以快速交货而闻名。

在这个问题中，日历按照第 天，第 天，第 天， 进行。

有订单 ，已知订单 将在第 天下单。
对于这些订单，运输根据以下规则进行。

• 最多可以同时发货 个订单。
• 订单 只能在第 天或之后发货。
• 一旦发货，下次发货必须至少相隔 天。
  • 也就是说，如果在第 天发货，下次发货将在第 天。

随着从下单到发货经过的每一天，不满增加 。
也就是说，如果订单 在第 天发货，则该订单的累积不满为 。

找出通过在最佳安排发货日期时所有订单上累积的最小可能总不满。

限制条件

• 所有输入值均为整数。

---

输入

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

输出

输出一个整数作为答案。

---

输入样例 1

5 2 3
1 5 6 10 12

输出样例 1

2

例如，通过以下发货安排，我们可以实现总不满为 ，即最小可能值。

• 在第 天发货订单 。
  • 这导致不满为 ，下次发货可以在第 天进行。
• 在第 天发货订单 和订单 。
  • 这导致不满为 ，下次发货可以在第 天进行。
• 在第 天发货订单 。
  • 这导致不满为 ，下次发货可以在第 天进行。
• 在第 天发货订单 。
  • 这导致不满为 ，下次发货可以在第 天进行。

---

输入样例 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