UCBINTI - Sequence

no tags 

We say that an integer sequence a1, a2, ... an is k-even if the sum of any k consecutive terms of the sequence is even.

For a given sequence we would like to find out how many of its terms need to be changed so that the sequence becomes k-even.

Input

The first line of input contains two integers n and k (1 ≤ k ≤ n ≤ 106). The second line contains a sequence composed of n integers a1, a2, ... an. For each of the ai's it holds that 0 ≤ ai ≤ 109.

Output

The only line of output should hold one integer: the minimum number of terms of the sequence that need to be changed so that it becomes k-even.

Example

Input:
8 3
1 2 3 4 5 6 7 8

Output:
3
Input:
8 3
2 4 2 4 2 4 2 4

Output:
0

hide comments
manav_66: 2023-05-24 16:27:06

I am getting up to 38 test cases. Tried a lot .can anyone help me out

chandan dwivedi: 2015-09-25 10:57:49

Those who solved it,please contribute it on spoj toolkit in order to make available more test cases for us....


Added by:Gabriel Menacho
Date:2014-09-10
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64