P12615 [RMI 2023] Heroes

翻译来自 [LibreOJ](https://loj.ac/p/4800)。

> —— 小明，你整天玩电脑游戏是在浪费生命啊！ > —— 没事的，妈妈，我还有三条命呢！ 在保卫世间一切美好事物的大战中，有 $H$ 位英雄正在与 $M$ 只怪兽激战。他们围成一个圈，按特定的顺序站好。第 $i$ 位英雄身后跟着 $m_i$ 只怪兽（总共有 $m_1 + m_2 + \dots + m_H = M$）。 战斗从第一位英雄开始，大家轮流挥剑进攻。英雄可以攻击圈中任意一只怪兽，而怪兽也能攻击任意一位英雄（无论位置远近）。每只怪兽挨上 $K$ 剑就会被消灭，而英雄们则是无敌的。 英雄们为了荣耀而战，希望尽可能少挨怪兽的攻击。请你计算，在消灭所有怪兽前，英雄们最少需要承受多少次攻击？

第一行包含两个整数 $H$ 和 $K$，用空格分隔。 第二行包含 $H$ 个用空格分隔的整数，分别是 $m_1, m_2, \ldots ,m_H$。

输出一个整数，表示英雄们最少需要承受的攻击次数。

### 样例 1 解释 这里有 $H=3$ 位英雄和 $M=6$ 只怪兽，每只怪兽的生命值为 $K=1$。初始站位是 `HHMMMHMMM`（`H` 表示英雄，`M` 表示怪兽）。前两位英雄分别消灭第一和第二只怪兽，第三只怪兽发起攻击。第三位英雄消灭第四只怪兽，最后两只怪兽也发动攻击。此时圈中变为 `HHMHMM`。第二轮时，每位英雄各消灭一只怪兽，之后英雄们不再受到攻击。 ### 数据范围与提示 对于所有输入数据，满足： * $1 \leq H \leq 3\ 000$ * $1 \leq M \leq 1\ 000 \ 000 \ 000$ * $1 \leq K \leq 1\ 000$ * 对于 $1 \leq i \leq H$，$0 \leq m_i \leq M$ * 答案保证不超过 $10^{18}$。 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :---: | :---: | :--: | | $1$ | $7$ | $H \leq 10$, $M \leq 4$, $K \leq 4$| | $2$ | $11$ | $H \leq 20$, $M \leq 10$, $K \leq 30$| | $3$ | $15$ | $M \leq 150\ 000$ | | $4$ | $17$ | $M \leq 5\ 000 \ 000$ | | $5$ | $19$ | $M \leq 30\ 000 \ 000$ | | $6$ | $31$ | 无附加限制 |