Sensor Blocking

Sensor Blocking

Problem Statement

As usual, Seth and Andy have stayed at uni until 3am the night before their exam.

Instead of studying for their exam, they are studying the motion sensor layout of the room in order to cover the sensors with sheets of foil, so that they can continue their degeneracy with the lights off and unable to automatically turn back on.

They model the room as an array $A$, with elements of $A$ corresponding to segments of the room. Each segment is either empty, or contains a single motion sensor with positive integer strength. Through countless hours of experimentation, Andy and Seth found that a sensor with strength $x$ requires at least $x$ overlapping sheets of foil in the sensor's segment to avoid detecting motion.

Conveniently, MAPS has a stash of sheets of foil, with each sheet capable of covering exactly $k$ consecutive segments. The supply isn't unlimited, however, so Andy and Seth have posed a conundrum: what is the minimum number of sheets required to fully cover every motion sensor?

Input

The first line contains two integers, $n$ and $k$, where $n$ is the size of the room, and $k$ is the size of each sheet of foil. The second line contains $n$ integers $a_1, a_2, … ,a_n$, where $a_i$ is $0$ if there is no sensor in segment $i$, or a positive integer corresponding to the strength of the sensor.

Output

The output consists of a single integer, the minimum number of sheets of foil required to block every sensor in the room.

Constraints

For test set 1:

• $1 \leq n \leq 10^{3}$
• $1 \leq k \leq 10^{3}$
• $1 \leq a_i \leq 10^{9}$

For test set 2:

• $1 \leq n \leq 10^{5}$
• $1 \leq k \leq 10^{5}$
• $1 \leq a_i \leq 10^{9}$

Sample Test Case

Example 1

6 2
0 2 1 1 3 1

5

Explanation

A possible solution, with lines of # marking a sheet of foil:

0 2 1 1 3 1
# #
  # #
        # #
      # #
      # #

It can be shown that no configuration with fewer sheets can cover every sensor.