cho.sh
Notes
Loading...

Repairing Pipe Leaks

Time limit

2s

Memory limit

128 MB

Problem

A water pipe is leaking at several points. Each leak is given as an integer distance from the left end of the pipe.

You may use any number of tapes, each of length L. To seal a leak, the tape must cover at least 0.5 units to the left and at least 0.5 units to the right of that leak. Tapes cannot be cut, but they may overlap.

Given the leak positions and the tape length L, find the minimum number of tapes needed to seal all leaks.

Input

The first line contains the number of leaks N and the tape length L. The second line contains N leak positions.

N and L are integers between 1 and 1,000, inclusive. Each position is an integer between 1 and 1,000, inclusive.

Output

Print the minimum number of tapes needed.