103531: [Atcoder]ABC353 B - AtCoder Amusement Park

Problem Statement

The AtCoder amusement park has an attraction that can accommodate $K$ people. Now, there are $N$ groups lined up in the queue for this attraction.

The $i$-th group from the front $(1\leq i\leq N)$ consists of $A_i$ people. For all $i$ $(1\leq i\leq N)$, it holds that $A_i \leq K$.

Takahashi, as a staff member of this attraction, will guide the groups in the queue according to the following procedure.

Initially, no one has been guided to the attraction, and there are $K$ empty seats.

1. If there are no groups in the queue, start the attraction and end the guidance.
2. Compare the number of empty seats in the attraction with the number of people in the group at the front of the queue, and do one of the following:
   • If the number of empty seats is less than the number of people in the group at the front, start the attraction. Then, the number of empty seats becomes $K$ again.
   • Otherwise, guide the entire group at the front of the queue to the attraction. The front group is removed from the queue, and the number of empty seats decreases by the number of people in the group.
3. Go back to step 1.

Here, no additional groups will line up after the guidance has started. Under these conditions, it can be shown that this procedure will end in a finite number of steps.

Determine how many times the attraction will be started throughout the guidance.

Constraints

• $1\leq N\leq 100$
• $1\leq K\leq 100$
• $1\leq A_i\leq K\ (1\leq i\leq N)$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

7 6
2 5 1 4 1 2 3

Sample Output 1

4

Initially, the seven groups are lined up as follows:

Part of Takahashi's guidance is shown in the following figure:

• Initially, the group at the front has $2$ people, and there are $6$ empty seats. Thus, he guides the front group to the attraction, leaving $4$ empty seats.
• Next, the group at the front has $5$ people, which is more than the $4$ empty seats, so the attraction is started.
• After the attraction is started, there are $6$ empty seats again, so the front group is guided to the attraction, leaving $1$ empty seat.
• Next, the group at the front has $1$ person, so they are guided to the attraction, leaving $0$ empty seats.

In total, he starts the attraction four times before the guidance is completed. Therefore, print 4.

Sample Input 2

7 10
1 10 1 10 1 10 1

Sample Output 2

7

Sample Input 3

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

Sample Output 3

8

问题描述

AtCoder 游乐园有一个能容纳 $K$ 人的游乐设施。现在，有 $N$ 个团队在该设施的排队队伍中。

队伍前面的第 $i$ 个团队 $(1\leq i\leq N)$ 有 $A_i$ 人。对于所有 $i$ $(1\leq i\leq N)$，都有 $A_i \leq K$。

作为该设施工作人员的高桥，将按照以下程序引导排队的队伍：

最初，没有团队被引导到设施，且有 $K$ 个空座位。

1. 如果队伍中没有团队，启动设施并结束引导。
2. 比较设施中的空座位数与队伍前面团队的人数，执行以下操作之一：
   • 如果空座位数少于队伍前面团队的人数，启动设施。然后，空座位数再次变为 $K$。
   • 否则，引导队伍前面的整个团队到设施。队伍前面的团队被移除，空座位数减少该团队的人数。
3. 返回步骤 1。

在引导开始后，不会有额外的团队排队。在这些条件下，可以证明该程序将在有限的步骤内结束。

确定在整个引导过程中设施将启动多少次。

约束

• $1\leq N\leq 100$
• $1\leq K\leq 100$
• $1\leq A_i\leq K\ (1\leq i\leq N)$
• 所有输入值都是整数。

输入

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

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

输出

打印答案。

样例输入 1

7 6
2 5 1 4 1 2 3

样例输出 1

4

最初，七个团队排队如下：

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

• 最初，队伍前面的团队有 $2$ 人，有 $6$ 个空座位。因此，他引导前面的团队到设施，留下 $4$ 个空座位。
• 接下来，队伍前面的团队有 $5$ 人，超过 $4$ 个空座位，所以启动设施。
• 设施启动后，再次有 $6$ 个空座位，所以引导前面的团队到设施，留下 $1$ 个空座位。
• 接下来，队伍前面的团队有 $1$ 人，所以他们被引导到设施，留下 $0$ 个空座位。

在引导完成之前，他共启动设施四次。 因此，打印 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