벽의 칼리

픽사베이에서 가져온 이미지

칼리는 벽에 유난히 큰 관심을 가진 뛰어난 목수이다. 오늘 칼리는 작업을 하나 맡았다. 새 아파트를 짓고 있으며, 이 아파트는 $N$개의 칸으로 주어진다. 각 칸은 *#*으로 표시되는 벽이거나 *-*로 표시되는 빈칸이다. 가장 왼쪽 칸과 가장 오른쪽 칸은 항상 벽이다.

칼리는 크기가 정확히 $M$인 방이 생기도록 최소 개수의 벽을 허물어 달라는 요청을 받았다. 즉, 정확히 $M$개의 빈칸이 나란히 있어야 하며, 그보다 많아서도 적어서도 안 된다. 가장 왼쪽이나 가장 오른쪽의 벽을 허물면 바깥으로 열리므로 칼리는 이 벽들을 허물 수 없다.

채점

그룹 | 점수 | 제한

1 | 28 | $N \leq 100$

2 | 32 | $N \leq 3\,000$

3 | 40 | 추가 제한 없음

입력의 첫째 줄에는 두 정수 $N$와 $M$ ($1 \leq M \leq N \leq 5\cdot 10^5$)가 주어지며, 각각 칸의 개수와 칼리가 만들어야 하는 방의 크기를 나타낸다.

다음 줄에는 아파트를 나타내는 $N$개의 문자로 이루어진 문자열이 주어진다.

위의 조건을 만족시키기 위해 칼리가 허물어야 하는 벽의 최소 개수를 한 줄에 출력한다. 불가능하다면 Neibb을 출력한다.