题目描述

题目译自 Romanian Master of Informatics 2023 Day1 T2 「Heroes」

—— 小明，你整天玩电脑游戏是在浪费生命啊！
—— 没事的，妈妈，我还有三条命呢！

在保卫世间一切美好事物的大战中，有 $H$ 位英雄正在与 $M$ 只怪兽激战。他们围成一个圈，按特定的顺序站好。第 $i$ 位英雄身后跟着 $m_i$ 只怪兽（总共有 $m_1 + m_2 + \dots + m_H = M$）。

战斗从第一位英雄开始，大家轮流挥剑进攻。英雄可以攻击圈中任意一只怪兽，而怪兽也能攻击任意一位英雄（无论位置远近）。每只怪兽挨上 $K$ 剑就会被消灭，而英雄们则是无敌的。

英雄们为了荣耀而战，希望尽可能少挨怪兽的攻击。请你计算，在消灭所有怪兽前，英雄们最少需要承受多少次攻击？

输入格式

第一行包含两个整数 $H$ 和 $K$，用空格分隔。

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

输出格式

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

3 1
0 3 3

3

这里有 $H=3$ 位英雄和 $M=6$ 只怪兽，每只怪兽的生命值为 $K=1$。初始站位是 HHMMMHMMM（H 表示英雄，M 表示怪兽）。前两位英雄分别消灭第一和第二只怪兽，第三只怪兽发起攻击。第三位英雄消灭第四只怪兽，最后两只怪兽也发动攻击。此时圈中变为 HHMHMM。第二轮时，每位英雄各消灭一只怪兽，之后英雄们不再受到攻击。

3 2
0 3 3

10

数据范围与提示

对于所有输入数据，满足：

• $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}$。

详细子任务附加限制及分值如下表所示。