410998: GYM104181 D Grumble Gym

Alberto loves working out. Unfortunately, he is single, and with Valentine's Day coming up, he has decided to work even harder. Each day, he will drink $$$N$$$ ($$$1 \leq N \leq 10^5$$$) new protein shakes throughout his workout, and each protein shake will give him $$$E_i$$$ units of energy ($$$1 \leq i \leq N$$$, $$$0 \leq E_i \leq 10^5$$$). Since he is superstitious, he always drinks his shakes in the order listed in the input, and once he starts drinking a shake he will finish it completely.

Today, his workout consists of doing as many sets of $$$M$$$ ($$$1 \leq M \leq 10^3$$$) pushups as possible. He needs $$$k$$$ units of energy to do the $$$kth$$$ pushup, and he will stop once he completes the current set. Once he completes a set, his energy level resets to $$$0$$$. He will continue doing sets until he runs out of protein shakes.

Given the units of energy in the protein shakes that he will drink today, how many complete sets of pushups will Alberto be able to complete?

The first line contains the integers $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$M$$$ ($$$1 \leq M \leq 10^3$$$).

The second line contains $$$N$$$ integers, $$$E_1, E_2, … E_N$$$ ($$$1 \leq i \leq N$$$, $$$0 \leq E_i \leq 10^5$$$).

A single integer representing the number of sets Alberto will complete.

4 5
2 20 80 4

2

3 3
20 5 2

1

In the first example, Alberto needs to use the first two energy drinks to make it through the first set (which takes $$$1+2+3+4+5$$$ units of energy), upon which his energy resets to $$$0$$$. The third energy drink gets him through the second set (which takes $$$6+7+8+9+10$$$ units of energy), and the last energy drink cannot get him through the third set.