You are given an array of n non negative elements. We can do atmost k swaps on the array. The swaps need not to be adjacent. Then we will divide the array into some contiguous disjoint subarrays. Your goal is to maximize the number of subarrays with and even sum.

Example 1
Consider n = 4, k = 1 arr[] = [1,2,3,4]

• Let's swap the array elements arr[1] with arr[2]. The new array is arr[] = [1,3,2,4]
• The division of array is 1,3 | 2 | 4

There is a total of 3 subarrays with an even sum.

Example 2
n = 6, k = 1, arr[] = [2, 1, 6, 7, 11, 5]
After swap, division of array will be 2 | 1, 7 | 6 | 11, 5
So answer will be 4

Example 3
n = 5, k = 2, arr[] = [1, 2, 3, 4, 5]
After 1 swap, division of array will be 1,3 | 2 | 4 | 5
So answer will be 3

Thanks