2018-2019 ICPC, NEERC, Southern Subregional Contest (Online Mirror, ACM-ICPC Rules, Teams Preferred) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Garbage Disposal

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputEnough 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

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/22/2019 00:14:58 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|