Special Dropkick 2

The buildings in NLCS Jeju are flimsy, so walls and doors can be broken with a dropkick.

The corridor of NLCS Jeju is divided into square zones numbered $0$ through $N$. Each zone except zone $0$, where Dongho stands, may contain an obstacle. Dongho wants to move from zone $0$ to zone $N$, where the classroom is, as quickly as possible.

Dongho has a string $S$ of length $N$ that describes the corridor. For each integer $1\le i\le N$, if $S_i$ is X, zone $i$ has an obstacle. If $S_i$ is ., zone $i$ has no obstacle.

Dongho can move obstacles at most $M$ times in the following ways.

• Push an obstacle one cell toward higher numbers. All consecutive obstacles in the direction of higher numbers move together.
• Push an obstacle one cell toward lower numbers. All consecutive obstacles in the direction of lower numbers move together.

After being pushed, the obstacles must still be within zones $1$ through $N$.

After moving obstacles at most $M$ times, Dongho reaches the classroom by combining two techniques.

• Spend 1 second to move one zone toward higher numbers. Dongho cannot move into a zone that has an obstacle.
• Spend 2 seconds to destroy an obstacle next to Dongho. Dongho can also destroy obstacles adjacent to the destroyed one. After destroying obstacles, Dongho moves to the position of a destroyed obstacle. If several were destroyed, Dongho can move to any of those positions.

Dongho wants to minimize the time to reach the classroom. Find how many seconds it takes to reach the classroom.

The first line contains $N$ and $M$, separated by a space.

The second line contains the string $S$ of length $N$ that describes the corridor. If $S_i$ is X, zone $i$ has an obstacle. If $S_i$ is ., zone $i$ has no obstacle.

Print the number of seconds it takes Dongho to reach the classroom, as an integer.

• $1 \le N \le 200\,000$
• $0 \le M \le N$