human
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 ≤ n ≤ 2⋅10^5, 1 ≤ k ≤ 10^9) — number of days to consider and bag's capacity. The second line contains n space separated integers a_i (0 ≤ a_i ≤ 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
"""
W
assistant
#Here is Python code to compute the minimum number of bags Vasya needs to dispose of all of his garbage for the given n days.
hat I cannot create, I do not understand.

https://github.com/Cheran-Senthil/PyRival
Copyright (c) 2018 Cheran Senthilkumar
"""
# IMPORTS---------------------------------------------------------------------#
from __future__ import division, print_function

import itertools
import sys
from atexit import register
from io import BytesIO

# import cmath
import math
# import operator as op
# import random
# from bisect import bisect_left as bl, bisect_right as br
# from collections import Counter, defaultdict, deque
# from copy import deepcopy
# from cPickle import dumps
# from decimal import Decimal, getcontext
# from difflib import SequenceMatcher
# from fractions import Fraction, gcd
# from heapq import heappop, heappush
# from Queue import PriorityQueue, Queue

# PYTHON3---------------------------------------------------------------------#
class dict(dict):
    def items(self):
        return dict.iteritems(self)

    def keys(self):
        return dict.iterkeys(self)

    def values(self):
        return dict.itervalues(self)

filter = itertools.ifilter
map = itertools.imap
zip = itertools.izip

input = raw_input
range = xrange

# FASTIO----------------------------------------------------------------------#
# sys.stdout = BytesIO()
# register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))
# sys.stdin = BytesIO(sys.stdin.read())

# input = lambda: sys.stdin.readline().rstrip()
# print = lambda *args: sys.stdout.write(' '.join(str(x) for x in args) + '\n')
# flush = sys.stdout.flush

# SETTINGS--------------------------------------------------------------------#
# getcontext().prec = 100
# sys.setrecursionlimit(32768)

# CONSTANTS-------------------------------------------------------------------#
MOD = 1000000007
INF = float('+inf')

ASCII_LOWERCASE = 'abcdefghijklmnopqrstuvwxyz'
ASCII_UPPERCASE = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

# MAIN------------------------------------------------------------------------#
def main():
    _, k = map(int, input().split(' '))
    a = map(int, input().split(' '))
   ...