특별한 드롭킥

NLCS Jeju의 구조는 생각보다 부실해서, 벽이나 문 등을 드롭킥으로 부술 수 있다.

NLCS Jeju의 복도는 1차원 수직선으로 모델링할 수 있으며, 동호의 현재 좌표는 $x=0$이다. 동호는 $x=N$에 있는 교실로 가고 싶다. 그러나, NLCS Jeju의 구조는 매우 부실하기에, $1 \le i \le N$인 어떤 정수 $i$에 대해서도 $x=i$에 장애물이 존재할 수 있다.

복도의 구조는 .과 X로 이루어진 길이 $N$의 문자열로 표현할 수 있다. $i$번째 문자는 $x=i$에 대한 장애물의 존재 여부를 의미한다. 문자열의 $i$번째 문자가 X라는 것은, $x=i$에 장애물이 존재함을 의미한다.

동호는 $x=N$에 도착하기 위해 다음과 같은 동작을 $1$번 이상 수행할 수 있다. 다음 두 동작에 대한 설명은 동호가 $x=i$에 있음을 가정하고 설명한다.

• $x=i+1$에 장애물이 없을 시, $x=i+1$로 이동한다. 이 동작에는 $1$의 시간이 소요된다.
• $x=i+1$부터 연속하여 존재하는 장애물을 모두 제거하고, 제거된 장애물 중 가장 $x$좌표가 큰 장애물의 좌표로 이동한다. 이 동작에는 $2$의 시간이 소요된다.

동호가 $x=0$에 있는 동안, 동호는 $1 \le i \le N$이고 $x=i$에 장애물이 존재하지 않는 정수 $i$를 골라서 $x=i$에 장애물을 설치하는 동작을 최대 $M$번 할 수 있다. 이 동작에는 시간이 소요되지 않는다.

복도의 구조가 주어졌을 때, 동호가 $x=N$에 도착하는 데 걸리는 최소 시간을 구하는 프로그램을 작성하여라.

첫째 줄에 $N$과 $M$이 공백을 사이에 두고 주어진다.

둘째 줄에 복도의 구조를 나타내는 길이 $N$의 문자열 $S$가 주어진다. $S$의 $i$번째 문자가 .이면 $x=i$에 아무것도 없음을 뜻하고, X면 장애물이 하나 존재하는 것이다.

첫째 줄에 동호가 $x=N$에 도착하는 데 걸리는 최소 시간을 출력한다.

• $1 \le N \le 200\\,000$
• $0 \le M \le N$
• $M$은 .의 개수보다 적거나 같다.