You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

一个娱乐设施一次可容纳 $K$ 人。现有 $N$ 组人排队游玩，每组 $A_i$ 人，同一组人必须在一起玩。（$A_i \le K$）

一开始娱乐设施上没人。分为以下情况：

$1$ . 如果没人在排队或剩余座位数量小于下一组人数，开始游戏，结束后清空。

$2$ . 如果剩余座位数量不小于下一组人数，让他们上来，剩余空位相应减少。

输出开始游戏的次数。

输入输出样例

输入

7 6
2 5 1 4 1 2 3

输出

4

输入

7 10
1 10 1 10 1 10 1

输出

7

限制与约定

对于 $50 \%$ 的数据 $1 \le N \le 100$ $1 \le k \le 100$

对于 $100 \%$的数据 $1 \le N \le 10^6$ $1 \le k \le 10^6$ $1 \le A_i \le k$ （$1 \le i \le N$） 人数均为整数

• 时间限制: $1 s$
• 空间限制: $256 MB$