Background

$\text{uuku}$ is learning the four basic arithmetic operations!

Problem Description

To check $\text{uuku}$'s learning results, $\text{bh1234666}$ gives an integer sequence $a_i$ of length $n$, and asks $\text{uuku}$ to perform $m$ operations on this sequence.

In each operation, you may choose any number $a_i$ in the sequence and change $a_i$ into one of the following four results: $a_i+2$, $a_i-2$, $a_i\times 2$, $\lfloor\frac{a_i}{2}\rfloor$.

$\text{bh1234666}$ wants the range (maximum value minus minimum value) of the whole sequence to be as large as possible after $m$ operations.

Obviously, $\text{uuku}$ did not study carefully, so he wants you to help answer this question.

Input Format

The first line contains two integers $n$ and $m$.

The second line contains $n$ integers, representing the sequence $a_i$.

Output Format

One line with one integer, representing the maximum possible range.

3 2
0 1 0 

6

Hint

Sample Explanation

In the first operation, add $2$ to $1$ to get $3$.

In the second operation, multiply $3$ by $2$ to get $6$.

The range is $6-0=6$.

Constraints

This problem uses bundled tests. There are $2$ $\text{subtask}$s, and the final score is the sum of the scores of all $\text{subtask}$s.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \textbf{Score} & \textbf{Special Constraints} \cr\hline 1 & 40 & n \le 5,m \le 5 \cr\hline 2 & 60 & \cr\hline \end{array}$$

For $100\%$ of the testdata, $2 \le n \le 10^6$, $1 \le m \le 10$, $0 \le a_i \le 10^9$.

Translated by ChatGPT 5