Woburn Challenge 2016-17 Round 1 - Senior Division

It's Halloween night in Haddonfield, Illinois. Not exactly in the mood for trick-or-treating, Laurie Strode has instead invited her friend, Michael Myers, to join her for a friendly game of hide and seek.

Laurie's house has a hallway with a number of rooms. The floor plan of this section of the house can be represented as a string with ~N~ ~(1 \le N \le 200\,000)~ characters, each of which is either a . (representing empty space) or a # (representing a wall). A room is a maximal consecutive sequence of empty space in this floor plan. That is, each room is either preceded by a wall or is at the start of the floor plan. Similarly, each room is followed by a wall or is at the end of the floor plan. The floor plan includes at least one room.

No doubt you're familiar with the rules of hide and seek - Laurie is hiding in one of the rooms, and it's Michael's job to find her. When he enters a room, he can immediately determine if Laurie is hiding anywhere in it, so he could simply visit each of the rooms in the hallway and be sure to find her eventually.

However, maybe he can do even better than that. Michael has a superb sense of hearing, so when he enters a room, he can also determine if Laurie is hiding in any of the rooms which are no further than ~D~ ~(1 \le D \le 10^9)~ units away from that room. The distance between two rooms (in units) is equal to the minimum distance between any parts of those rooms in the floor plan (in characters). For example, if the floor plan is .#..##.., then the distance between the left room and the middle room is ~2~, the distance between the middle room and the right room is ~3~, and the distance between the left room and the right room is ~6~.

Michael is certainly looking forward to winning this game of hide and seek, but he values efficiency. He's wondering - what's the minimum number of rooms which he must enter in order to guarantee that he'll determine Laurie's location, no matter which room she's hiding in? In particular, to ensure victory, every room in the hallway must be within ~D~ units of at least one of Michael's chosen rooms.

In test cases worth ~3/15~ of the points, ~N \le 1\,000~ and ~D = 1~.
In test cases worth another ~6/15~ of the points, ~N \le 1\,000~.

Input Specification

The first line of input consists of two space-separated integers ~N~ and ~D~.
The second line consists of a single string representing the floor plan.

Output Specification

Output one line consisting of a single integer - the minimum number of rooms which Michael must enter to determine Laurie's location.

Sample Input

22 4
..#.#...##.#.....###.#

Sample Output

2

Sample Explanation

There are ~6~ rooms in the house. If Michael enters the ~3^{rd}~ room from the left, he'll be able to hear if Laurie is in any of the ~4~ leftmost rooms. If he enters the ~5^{th}~ room from the left, he'll be able to hear if she's in any of the ~3~ rightmost rooms. Therefore, entering the ~3^{rd}~ and ~5^{th}~ rooms from the left will be sufficient. Entering the ~3^{rd}~ and ~6^{th}~ rooms from the left would also do the job.