[ABC353] B - AtCoder Amusement Park

B - AtCoder Amusement Park

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 200 分

题面

AtCoder 游乐园有一项容纳 人的游乐项目。
现在，排了 组队的游客在等待排队进入这个游乐项目。

从队头开始的第 组 有 人。
对于所有 ，满足 。

高桥作为这个游乐项目的工作人员，将根据以下步骤引导等待的游客：

起初，还没有游客被引导进入游乐项目，游乐项目有 个空位。

1. 如果队伍中没有任何游客，则开始游乐项目并结束引导。
2. 比较游乐项目中的空位数和队伍队头的游客人数，执行以下操作之一：
   • 如果空位数少于队头的游客人数，则开始游乐项目。此时，游乐项目的空位数恢复为 。
   • 否则，引导队头的整个队伍进入游乐项目。队头的队伍离开队伍队列，空位数减少到队伍的人数。
3. 回到步骤 1。

在这里，引导开始后不会再有额外的队伍加入。在这些条件下，可以证明这个引导程序会在有限步内结束。

求确定引导过程中游乐项目会启动多少次。

限制条件

• 所有输入值均为整数。

---

输入

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

输出

输出答案。

---

输入样例 1

7 6
2 5 1 4 1 2 3

输出样例 1

4

起初，七组队伍排成如下：

高桥引导的部分过程如下图所示：

• 起初，队头的队伍有 人，游乐项目有 个空位。因此，他引导队头的队伍进入游乐项目，剩下 个空位。
• 接下来，队头的队伍有 人，超过了 个空位，所以游乐项目启动。
• 游乐项目启动后，又有 个空位，所以队头的队伍再次进入游乐项目，剩下 个空位。
• 接着，队头的队伍有 人，所以他们被引导进入游乐项目，空位并变为 。

总共在引导完成前，游乐项目启动了四次。因此，输出 4。

---

输入样例 2

7 10
1 10 1 10 1 10 1

输出样例 2

7

---

输入样例 3

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

输出样例 3

8