You are given an array of $N$ numbers.

An operation on the array is defined as :

Select a non-empty subarray of the array and a number $j$. Now flip the $j$-th bit of all the elements of this subarray.

Output the minimum sum of the elements of the given array that can be obtained after doint the above operation at most $K$ times.

Input Format

The first line contains two integers $N$ and $K$ ($1 \le N \le 10^5$, $1 \le K \le 10^9$), denoting the number of elements in the array and the maximum number of operations allowed.

The second line contains $N$ integers $A_1, A_2, \ldots, A_n$ ($1 \le A_i \le 10^6$), the elements of the array.

Output Format

Output the minimum sum of elements that can be obtained by applying the operation at most $K$ times.