AtCoder 游乐园

题目描述

AtCoder 游乐园有一个每次可容纳 $K$ 人的游乐设施。现在,该设施前有 $N$ 个团体排成一队。

从队首数起第 $i$ 个团体 $(1\le i\le N)$ 有 $A_i$ 人。对于所有 $i$ $(1\le i\le N)$,有 $A_i \le K$。

身为该设施工作人员的高桥君,将按照以下步骤引导队伍中的团体。

1. 最初,尚未引导任何人进入设施,空位数为 $K$。
2. 若队伍中没有团体,则启动设施,引导结束。
3. 比较设施中的空位数与队首团体的人数,并执行以下操作之一:
   • 若空位数少于队首团体的人数,则启动设施。之后,空位数再次变为 $K$。
   • 否则,将队首的整个团体引导进设施。队首团体从队伍中移除,空位数减少该团体的人数。
4. 回到步骤 1。

这里,引导开始后不会有新的团体加入队伍。在这些条件下,可以证明该步骤会在有限步内结束。

求在整个引导过程中,设施一共被启动了多少次。

输入格式

输入按以下格式从标准输入给出:

$N$ $K$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出答案。

样例

7 6
2 5 1 4 1 2 3

4

最初,七个团体排成如下队伍:

队首团体有 $2$ 人,空位数为 $6$,因此高桥君将队首团体引导进设施,剩余 $4$ 个空位。

接下来,队首团体有 $5$ 人,多于 $4$ 个空位,因此启动设施。

设施启动后,空位数再次变为 $6$,于是队首团体被引导进设施,剩余 $1$ 个空位。

接着,队首团体有 $1$ 人,因此他们被引导进设施,空位数变为 $0$。

在整个引导完成前,他总共启动了设施 4 次。因此输出 4。

7 10
1 10 1 10 1 10 1

7

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

8

数据范围

• $1\le N\le 100$
• $1\le K\le 100$
• $1\le A_i\le K\ (1\le i\le N)$
• 输入中的所有值均为整数