P8480 "HGOI-1" PMTD

$\text{uuku}$ is learning [the four basic arithmetic operations](https://baike.baidu.com/item/%E5%9B%9B%E5%88%99%E8%BF%90%E7%AE%97/5337481?fr=aladdin)!

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.

The first line contains two integers $n$ and $m$. The second line contains $n$ integers, representing the sequence $a_i$.

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

#### 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