题目描述

宇航员鲍勃正在外太空执行任务，他所在的星球上有各种不同的物质。他需要为研究室收集零碎的小陨石，但这个工作太费力，所以他自己不会进行搬运，而是向研究室申请了一台搬运机器人。但是搬运机器人每次搬运的重量是有限的，因此鲍勃需要合理分配机器人的搬运任务，使得机器人运送的总次数最少。

​机器人的负重上限是 $m$，总共有 $n$ 枚陨石碎片需要搬运，第 $i$ 块陨石碎片的重量是 $a_i$。请计算：搬运机器人最少要运送几次，才能搬完全部的陨石碎片？

注意：由于每一枚碎片之间的距离较远，因此机器人无法调整碎片的顺序，只能按照前进的方向依次收集陨石碎片。

输入格式

​第一行：两个整数 $n,m$，分别表示陨石碎片的数量和机器人的负重上限。

第二行：$n$ 个整数 $a_i,a_2,...,a_n$，分别表示每块陨石碎片的重量。

输出格式

一个整数，表示最少的运送次数。

5 6
1 3 1 2 4

2

8 5
1 4 2 3 4 5 4 3

6

3 10
1 8 9

2

样例 $1$ 解释

第一次可以搬运 $1+3+1=5$ 的重量，剩下的两块碎片重量为 $2+4=6$，需要第二次搬运。

数据范围

对于 $20\%$ 的数据，$1≤n≤10$；

对于 $40\%$ 的数据，$1≤n≤1000$；

对于 $100\%$ 的数据，$1≤n≤10^5，1≤a_i≤m≤10^9$，且 $a_i$ 之和不超过 $10^9$。