We say that an integer sequence a₁, a₂, ... , a_n 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 ≤ 10⁶). The second line contains a sequence composed of n integers a₁, a₂, ... , a_n. For each of the a_i's it holds that 0 ≤ a_i ≤ 10⁹.

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