Enough is enough. Too many times it happened that Vasya forgot to dispose of garbage and his apartment stank afterwards. Now he wants to create a garbage disposal plan and stick to it.

For each of next $n$ days Vasya knows $a_i$ — number of units of garbage he will produce on the $i$-th day. Each unit of garbage must be disposed of either on the day it was produced or on the next day. Vasya disposes of garbage by putting it inside a bag and dropping the bag into a garbage container. Each bag can contain up to $k$ units of garbage. It is allowed to compose and drop multiple bags into a garbage container in a single day.

Being economical, Vasya wants to use as few bags as possible. You are to compute the minimum number of bags Vasya needs to dispose of all of his garbage for the given $n$ days. No garbage should be left after the $n$-th day.


-----Input-----

The first line of the input contains two integers $n$ and $k$ ($1 \le n \le 2\cdot10^5, 1 \le k \le 10^9$) — number of days to consider and bag's capacity. The second line contains $n$ space separated integers $a_i$ ($0 \le a_i \le 10^9$) — the number of units of garbage produced on the $i$-th day.


-----Output-----

Output a single integer — the minimum number of bags Vasya needs to dispose of all garbage. Each unit of garbage should be disposed on the day it was produced or on the next day. No garbage can be left after the $n$-th day. In a day it is allowed to compose and drop multiple bags.


-----Examples-----
Input
3 2
3 2 1

Output
3

Input
5 1
1000000000 1000000000 1000000000 1000000000 1000000000

Output
5000000000

Input
3 2
1 0 1

Output
2

Input
4 4
2 8 4 1

Output
4

Difficulty: competition

Starter code:

Solutions:
n,k=list(map(int,input().split()))
arr=list(map(int,input().split()))
ans=arr[0]//k
val=arr[0]%k
for i in range(1,n):
    if(val==0):
        ans+=arr[i]//k
        val=arr[i]%k
    else:
        val+=arr[i]
        if(val<k):
            val=0
            ans+=1
        else:
            ans+=val//k
            val=val%k
if(val!=0):
    ans+=1
print(ans)


from math import ceil
n, k = list(map( int, input().split() ))
a = [ 0 ] + list( map( int, input().split() ) )

last = 0
bags = 0
for i in range( n + 1 ):
    if i == n:
        last += a[ i ]
        bags += ceil( last / k )
    else:
        b = ceil( last / k )
        bags += b
        l = b * k - last
        last = a[ i ] - min( a[ i ], l )

print( bags )



n,k=[int(x) for x in input().split()]
a=[int(x) for x in input().split()]
ans=0
pre=0
for i in range(n):
    if pre!=0:
        ans+=1
        a[i]-=(k-pre)
        if a[i]<0:a[i]=0
    ans+=a[i]//k
    pre=a[i]-a[i]//k*k
if pre!=0 : ans+=1
print(ans)

n, k = map(int, input().split())
l = [*map(int, input().split())]
c = 0
res = 0
for i, e in enumerate(l):
    if (e + c) < k and c > 0:
        res += int((e + c) > 0)
        c = 0
    else:
        res += (e + c) // k
        c = (e + c) % k
if c > 0: res += 1
print(res)

import math as ma
import sys
from decimal import Decimal as dec
from itertools import permutations

def li():
	return list(map(int , input().split()))

def num():
	return map(int , input().split())

def nu():
	return int(input())

def find_gcd(x , y):
	while (y):
		x , y = y , x % y
	return x

n,k=num()
a=li()
z=0
x=0
for i in range(n):
	if(z%k==0):
		x+=int(ma.ceil(z/k))+a[i]//k
		z = a[i] % k
	else:
		cp=z%k
		zz=a[i]-(k-cp)
		if(zz<0):
			zz=0
		x+=int(ma.ceil(z/k))+zz//k
		z=zz%k
if(z>0):
	x+=1
print(x)

from math import floor
n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
i=0
rem=0
while i<n:
    if i<n-1:
        if a[i]+rem<=k and rem!=0:
            ans+=1
            i+=1
            rem=0
        else:
            ans+=floor((a[i]+rem)/k)
            rem=(a[i]+rem)%k
            i+=1
    elif i==n-1:
        ans+=floor((a[i]+rem)/k)
        rem=(a[i]+rem)%k
        i+=1
if rem!=0:
    ans+=1
print(ans)

n, k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
p = 0
cp = 0
sdg = 0
fdg = 0
tg = 0
fplp = 0
for d in range(n-1):
    fdg = a[d]
    cp = sdg // k + (0 if sdg % k == 0 else 1)
    fplp = k - sdg % k
    if fplp == k:
        fplp = 0
    fdg -= min(fplp, fdg)
    cp += fdg // k
    fdg -= (fdg // k) * k
    p += cp
    sdg = fdg
fdg = a[n-1]
p += (sdg + fdg) // k + (0 if (sdg + fdg) % k == 0 else 1)
print(p)


n,k = list(map(int,input().split()))
arr = list(map(int,input().split()))
prev = 0;
bags = 0;
for i in range(n):
	if (arr[i]+prev)//k == 0:
		if prev > 0:
			bags+=1;
			prev=0;
		else:
			prev = arr[i];
	else:
		bags += (arr[i]+prev)//k;
		prev = (arr[i]+prev)%k
if prev!=0:
	bags+=1
print(bags)




import math
n,k=[int(s) for s in input().split()]

a=[int(s) for s in input().split()]

def check():
    n=len(a)
    res=0
    sum0=0
    for i in range(n):
        res0=res
        if res==0 :
            if a[i]<k:
                res=a[i]
                if i==n-1 and a[i]!=0:
                    sum0+=1
            else:
                if i==n-1:
                    sum0+=math.ceil((a[i])/k)
                else:
                    sum0 += int((a[i]) / k)
                res=a[i]%k
        else:
            if i == n - 1:
                sum0+=math.ceil((a[i]+res)/k)
            else:
                sum0 += max(int((a[i] + res) / k),1)
            #print(res, max(int((a[i] + res) / k), 1))
            res = (a[i] + res) % k if a[i] + res >= k else 0
        #print(res0,sum0)
    print(sum0)

check()

n, k = [int(x) for x in input().split()]
lst = [int(x) for x in input().split()]
x=0
s=0
ans=0
for i in range(n):
        if x==0:
                s+=lst[i]
                ans+=(s//k)
                s=s%k
                if s>0: x=1
        elif x==1:
                if (s+lst[i]<k):
                        ans+=1
                        s=0
                        x=0
                else:
                        s+=lst[i]
                        ans+=s//k
                        s=s%k
                        if s>0: x=1
                        else: x = 0
        #print(s,ans)
                        
                        
if(s>0):
        print(ans+1)
else:
        print(ans)
                


n, m = map(int, input().split())

a = list(map(int, input().split()))

res = 0
sum = 0
can = True

for i in range(n):
    if sum > 0:
        sum = sum + a[i]
        if sum < m:
            res = res + 1
            sum = 0
        else:
            res = res + sum // m
            sum = sum % m
    else:
        sum = sum + a[i]
        res = res + sum // m
        sum = sum % m
        
if sum > 0:
    res = res + 1
print(res)

n,k =list(map(int,input().split()))

a=[int(x) for x in input().split()]
bag=a[0]//k
remain=a[0]%k
for i in range(1,n):
    tk=a[i]+remain
    remain=tk%k
    if remain>a[i]:
        bag+=1
        remain=0
    else:
        bag+=tk//k
    
if remain==0:
    print(bag)
   
        
else:  
        
    print(bag+1)        


def read():
    return list(map(int, input().split()))

def solve(n, k, A):
    ans, prev = 0, 0
    for a in A:
        total = prev + a
        if prev and total < k:
            ans += 1
            total = 0
        elif total >= k:
            ans += total // k
            total %= k
        prev = total        
    ans += prev // k
    ans += 1 if prev % k > 0 else 0
    return ans

n, k = read()
A = read()
print(solve(n, k, A))

import math
n,k=map(int,input().split(" "))
plan=list(input().split())
plan=[int(x) for x in plan]
count=0
temp=0
for i in range(len(plan)):
    if i==n-1:
        if temp==0:
            count+=math.ceil(plan[i]/k)
            break
        else:
            plan[i]-=(k-temp)
            count+=1
            temp=0
            if plan[i]<0:
                plan[i]=0
            count+=math.ceil(plan[i]/k)
            break
    if temp!=0:
        plan[i]-=(k-temp)
        count+=1
        temp=0
        if plan[i]<0:
            plan[i]=0
    count+=int(plan[i]/k)
    temp=plan[i]%k
print(int(count))

v = []
n,k = list(map(int, input().split()))
s = 0
v = [int(x) for x in input().split()]
q = 0
carry = 0
for i in range(len(v)):
    prev_carry = carry
    garbage = v[i] + carry
    boxes = garbage // k
    carry = garbage % k
    if i > 0 and boxes == 0 and carry > 0 and prev_carry > 0:
        carry = 0
        boxes = 1
    q += boxes
if carry > 0:
    q += 1
print(q)


n, k = list(map(int,input().split()))
a = [int(x) for x in input().split()]
res = 0
for i in range(1, n):
	s = a[i - 1] + a[i]
	q = s // k
	res += q

	if q == 0 and a[i - 1] != 0:
		res += 1
		a[i] = 0
	else:
		a[i] = a[i] - (q * k - a[i - 1])
res += (a[n - 1] + k - 1) // k
print(res)


n,k = list(map(int, input().split()))
s = list(map(int,input().split()))

old = 0
current = 0
idx = 0
ans = 0
while idx < len(s):
    if(old != 0 and s[idx] // k == 0):
        ans+= 1
        old = max(s[idx] - (k-old),0)
        idx+=1
        continue
    ans += (s[idx]+old) // k
    old = (s[idx]+old) % k
    idx+=1
if(old>0):
    ans+=1
print(ans)


n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for i in range(0, len(a) - 1):
    
    ans += a[i] // k
    ans += int((a[i] % k) != 0)
    a[i + 1] += a[i] % k
    a[i + 1] = max(a[i + 1] - int((a[i] % k) != 0) * k, 0)
ans += a[len(a) - 1] // k + int(a[-1] % k != 0)
print(ans)




n, k = list(map(int, input().split()))
days = list(map(int, input().split()))

nb_bags=0
crt_cap=0
for i in range(n):
	if crt_cap !=0:
		days[i] = max(days[i]-(k-crt_cap), 0)
		crt_cap = 0
		nb_bags += 1
	nb_bags += int(days[i]/k)
	crt_cap = days[i]%k

if crt_cap !=0:
	nb_bags += 1

print(nb_bags)
	




n, k = list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
a.append(0)
ans = 0
for i in range(1, n + 2):
    t = (a[i - 1] + a[i]) // k
    if t > 0:
        ans += t
        t = (t * k) - a[i - 1]
        a[i] -= t
    else:
        if a[i - 1] > 0:
            ans += 1
            a[i] = 0
print(ans)


n,k = list(map(int,input().split()))
a = list(map(int,input().split()))+[0]
ans = 0
r = 0
for i in range(n-1,-1,-1):
    s = a[i]
    s = max(0,a[i]-r)
    x = (s+k-1)//k
    ans+=x
    r = x*k-s
    
print(ans)
        
        


from math import ceil

n, k = tuple(map(int, input().split()))
a = list(map(int, input().split()))
s = 0
r = 0
for i in range(n - 1, -1, -1):
    a[i] = max(0, a[i] - r)
    s += int(ceil(a[i] / k))
    if (a[i] % k) != 0:
        r = k - (a[i] % k)
    else:
        r = 0
print(s)


n, k = map(int, input().split())
l =  [*map(int, input().split())]
c = 0
res = 0

for i,val in enumerate(l):
    if (val + c) < k and c > 0:
        res += int((val+c)>0)
        c = 0
    else:
        res += (val+c)//k
        c = (val+c)%k
if c > 0: res += 1
print(res)

n, k = map(int, input().split())

r = 0
m = 0

for i in input().split():
  a = int(i) + m
  if (a < k):
    if (m != 0):
      r += 1
      m = 0
    else:
      m = a
  
  else:
    r += a // k
    m = a % k

r += (m + k - 1) // k
print(r)

n,k = map(int, input().split())
a = [0]+list(map(int, input().split()))
a.append(0)
bag = 0
for i in range(1, n + 2):
    t = (a[i-1]+a[i])//k
    if(t>0):
        bag += t
        t = (t*k)-a[i-1]
        a[i] -= t
    else:
        if(a[i-1]>0):
            bag += 1
            a[i] = 0
print(bag)