시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 250 73 59 43.382%

문제

불면의 밤을 지새워 본 사람이라면 잠 못 드는 그 시간이 얼마나 괴로운지 알고 있다. 잠을 자지 못하는 것은 다음날 피로를 야기하고 삶에 전반적으로 악영향을 미친다. 이러한 이유 때문에 숙면을 신의 축복이라고 부르기도 한다.

하지만 바쁜 현대인들에게 숙면을 취한다는 것은 마냥 쉬운 일이 아니다. 이런 상황을 안타깝게 여긴 인하대학교의 잠마니 박사는 숙면을 취할 수 있는 몇 가지 조건을 제시했다. 아래는 잠마니 박사가 제시한 숙면의 조건 중 일부를 보여준다.

1. 침대 주변을 어둡게 한다.
2. 자려고 하는 시간보다 일어나는 시간을 조정하려 한다.
..... 이하 생략 .....

극심한 불면증에 시달려 심신이 피폐해진 준형이는 잠마니 박사가 제시한 숙면의 조건을 지켜 잃어버린 정상적인 삶과 건강을 되찾을 수 있게 되었다. 여행을 갈 수 있을 만큼 건강해진 준형이는 기념으로 특별한 여행을 하고 싶었고 인터넷을 통해 특별한 숙소를 예약했다. 하지만 숙소에 도착하고 경악을 금치 못했는데, 그곳에는 정말로 특별한 전구들이 있었기 때문이다.

특별한 전구들은 N개가 일렬로 놓아져 있었고 각각의 전구들은 꺼져있거나 켜져 있었다. 모든 전구를 다 끄고 싶었지만 정말로 특별한 전구들이기 때문에 각각의 전구를 개별적으로 끄거나 켤 수 있는 스위치는 없고 정확하게 연속된 K개의 전구의 상태를 반전시킬 수 있는 버튼만이 있었다. (상태를 반전시킨다는 것은 꺼져있는 전구는 켜지고 켜져있는 전구는 꺼지는 것을 의미한다.)

최대한 빨리 잠이 들고 싶었던 준형이는 최소한의 버튼 조작으로 모든 전구를 다 끄고 싶었지만 최소한은 고사하고 모든 전구를 끄는 것조차 번번이 실패를 하였다. 이대로라면 숙면의 첫 번째 조건을 만족하지 못해 다시 불면증에 빠질 것은 자명한일!! 준형이를 도와 최소한의 버튼 조작으로 모든 전구를 끌 수 있는 프로그램을 작성하자.

아래는 N = 6이고 K = 3일 때 세 번의 버튼 조작으로 모든 전구를 끄는 과정을 보여준다. 세 번의 버튼 조작은 최소한의 조작 횟수이며 이보다 더 적게 조작을 해서 전구를 모두 끄는 방법은 존재하지 않는다.

[그림 1] 세 번의 버튼조작으로 전구를 끄는 과정

입력

입력의 첫 줄에는 특별한 전구의 개수 N(1 ≤ N ≤ 100,000)과 한 번의 버튼 조작으로 상태를 반전시킬 수 있는 전구의 개수 K(1 ≤ K ≤ N)가 주어진다.

다음 줄에는 N개의 Si가 공백을 기준으로 주어진다. Si는 i(1 ≤ i ≤ N)번째 전구의 상태를 나타내며 1은 전구가 켜져 있는 것을, 0은 전구가 꺼져있는 것을 의미한다. 

출력

모든 전구를 끌 수 있는 최소한의 버튼의 조작 횟수를 출력한다. 한 번의 조작은 정확히 연속된 K개 전구의 상태를 반전시킬 수 있음에 유의한다. 만약 어떠한 조작으로도 모든 전구를 끄는 것이 불가능하다면 “Insomnia”(따옴표는 제외)를 출력한다.

예제 입력

6 3
1 1 0 0 0 1

예제 출력

3

예제 입력 2

6 3
1 1 0 0 1 1

예제 출력 2

Insomnia

힌트