시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 225 69 57 34.545%

문제

정수 수열 a1, a2, ..., an이 있을 때, 1 ≤ i ≤ n − k + 1 인 모든 정수 i에 대해서, ai + ai+1 + ... + ai+k−1 이 짝수라면, 이 수열을 k-짝합 수열이라고 정의한다.

당신은 수열에 있는 몇 개의 원소를 원하는 정수로 바꿀 수 있다. 최소 몇 개의 원소를 바꿔야지 수열을 k-짝합 수열로 만들 수 있는가?

입력

첫번째 줄에는 정수 n, k가 주어진다. (1 ≤ k ≤ n ≤ 106)

두번째 줄에는 n개의 정수가 주어진다. 이 중 i 번째 정수는 ai(0 ≤ ai ≤ 109) 를 뜻한다.

출력

바꿔야 하는 원소의 최소 개수를 출력한다.

예제 입력 1

8 3
1 2 3 4 5 6 7 8

예제 출력 1

3
W3sicHJvYmxlbV9pZCI6Ijc5NzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM1ZjQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzgxNVx1YzIxOCBcdWMyMThcdWM1ZjQgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+XHVjNzc0IFx1Yzc4OFx1Yzc0NCBcdWI1NGMsIDEgJmxlOyBpICZsZTsgbiAmbWludXM7IGsgKyAxIFx1Yzc3OCBcdWJhYThcdWI0ZTAgXHVjODE1XHVjMjE4IGlcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBhPHN1Yj5pPFwvc3ViPiArIGE8c3ViPmkrMTxcL3N1Yj4gKyAuLi4gKyBhPHN1Yj5pK2smbWludXM7MTxcL3N1Yj4gXHVjNzc0IFx1YzlkZFx1YzIxOFx1Yjc3Y1x1YmE3NCwgXHVjNzc0IFx1YzIxOFx1YzVmNFx1Yzc0NCBrLVx1YzlkZFx1ZDU2OSBcdWMyMThcdWM1ZjRcdWM3NzRcdWI3N2NcdWFjZTAgXHVjODE1XHVjNzU4XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZjlcdWMyZTBcdWM3NDAgXHVjMjE4XHVjNWY0XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWJhODcgXHVhYzFjXHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yjk3YyBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVjODE1XHVjMjE4XHViODVjIFx1YmMxNFx1YWZjMCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWNkNWNcdWMxOGMgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWM2ZDBcdWMxOGNcdWI5N2MgXHViYzE0XHVhZmQ0XHVjNTdjXHVjOWMwIFx1YzIxOFx1YzVmNFx1Yzc0NCBrLVx1YzlkZFx1ZDU2OSBcdWMyMThcdWM1ZjRcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWFjMDA/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxNVx1YzIxOCBuLCBrXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBrICZsZTsgbiAmbGU7IDEwPHN1cD42PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+XHViNDUwXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWM5MTEgaSBcdWJjODhcdWM5ZjggXHVjODE1XHVjMjE4XHViMjk0IGE8c3ViPmk8XC9zdWI+KDAgJmxlOyBhPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPikgXHViOTdjIFx1YjczYlx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWJjMTRcdWFmZDRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzZkMFx1YzE4Y1x1Yzc1OCBcdWNkNWNcdWMxOGMgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI3OTc2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2VxdWVuY2UiLCJkZXNjcmlwdGlvbiI6IjxwPldlIHNheSB0aGF0IGFuIGludGVnZXIgc2VxdWVuY2UgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+IGlzIGstZXZlbiBpZiB0aGUgc3VtIG9mIGFueSBrIGNvbnNlY3V0aXZlIHRlcm1zIG9mIHRoZSBzZXF1bmNlIGlzIGV2ZW4uPFwvcD5cclxuXHJcbjxwPkZvciBhIGdpdmVuIHNlcXVlbmNlIHdlIHdvdWxkIGxpa2UgdG8gZmluZCBvdXQgaG93IG1hbnkgb2YgaXRzIHRlcm1zIG5lZWQgdG8gYmUgY2hhbmdlZCBzbyB0aGF0IHRoZSBzZXF1ZW5jZSBiZWNvbWVzIGstZXZlbi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBuIGFuZCBrICgxICZsZTsgayAmbGU7IG4gJmxlOyAxIDAwMCAwMDApLiBUaGUgc2Vjb25kIGxpbmUgY29udGFpbnMgYSBzZXF1ZW5jZSBjb21wb3NlZCBvZiBuIGludGVnZXJzIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgLi4uLCBhPHN1Yj5uPFwvc3ViPi4gRm9yIGVhY2ggb2YgdGhlIGFpJnJzcXVvO3MgaXQgaG9sZHMgdGhhdCAwICZsZTsgYTxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDAgMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBob2xkIG9uZSBpbnRlZ2VyOiB0aGUgbWluaW11bSBudW1iZXIgb2YgdGVybXMgb2YgdGhlIHNlcXVlbmNlIHRoYXQgbmVlZCB0byBiZSBjaGFuZ2VkIHNvIHRoYXQgaXQgYmVjb21lcyBrLWV2ZW4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d