— 比利，你整天沉迷于电脑游戏，简直是在浪费生命！ — 没关系，妈妈，我还有三条命呢！
在拯救世间一切美好的伟大战斗中，$H$ 位英雄正在与 $M$ 只怪物组成的军团作战。战斗人员按给定的顺序站成一个圆圈。第 $i$ 位英雄之后紧跟着 $m_i$ 只怪物（满足 $m_1 + m_2 + \dots + m_H = M$）。
从第一位英雄开始，战斗人员轮流挥剑攻击。英雄可以攻击任意一只怪物，而怪物也可以攻击任意一位英雄（圆圈上的任何位置）。一只怪物受到 $K$ 次攻击后会被消灭。英雄是无敌的。
任务
英雄们为了荣誉而战，希望受到的攻击次数尽可能少。在消灭所有怪物之前，英雄们最少会受到多少次攻击？
输入格式
第一行包含两个整数 $H$ 和 $K$，中间用空格分隔。
第二行包含 $H$ 个用空格分隔的整数 $m_1, m_2, \dots, m_H$。
输出格式
输出一个整数，表示英雄们受到的最少攻击次数。
数据范围
- $1 \leq H \leq 3 \ 000$
- $1 \leq M \leq 1 \ 000 \ 000 \ 000$
- $1 \leq K \leq 1 \ 000$
- $0 \leq m_i \leq M$ 对于 $1 \leq i \leq H$
- 答案保证不超过 $10^{18}$。
| # | 分值 | 数据范围 |
|---|---|---|
| 0 | 0 | 样例 |
| 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 | 无额外限制 |
样例
输入格式 1
3 1 0 3 3
输出格式 1
3
说明
这里有 $H=3$ 位英雄和 $M=6$ 只怪物，每只怪物有 $K=1$ 点生命值。初始顺序为 HHMMMHMMM（其中 H 代表英雄，M 代表怪物）。前两位英雄消灭了前两只怪物。第三只怪物发动攻击。第三位英雄消灭了第四只怪物。最后两只怪物发动攻击。此时圆圈变为 HHMHMM。第二轮时，每位英雄消灭一只怪物，英雄们不再受到攻击。
输入格式 2
3 2 0 3 3
输出格式 2
10