Maximizing Range After Sequence Operations

You are given an integer sequence \(a_1, a_2, \dots, a_n\) and an integer \(m\) representing the total number of operations. In each operation you can choose any element \(a_i\) and replace it with one of the following four values:

• \(a_i+2\)
• \(a_i-2\)
• \(a_i\times2\)
• \(\lfloor\frac{a_i}{2}\rfloor\)

Your goal is to maximize the range (i.e. the difference between the maximum and minimum values) of the sequence after exactly \(m\) operations.

Note: Operations may be applied to the same element more than once and they can be distributed arbitrarily among the elements. Formally, if you denote by \(f_{\max}(x,k)\) the maximum value that can be obtained from a number \(x\) after applying \(k\) operations optimally and by \(f_{\min}(x,\ell)\) the minimum value obtainable from \(x\) after \(\ell\) operations optimally, then the answer is:

[ \max_{0\le k\le m}\Bigl( \max_{1\le i\le n} f_{\max}(a_i,k) - \min_{1\le j\le n} f_{\min}(a_j, m-k) \Bigr). ]

The functions \(f_{\max}\) and \(f_{\min}\) are defined as follows:

• For maximizing (\(f_{\max}(x,k)\)):
  • If \(k = 0\), then \(f_{\max}(x,0)=x\).
  • If \(x > 0\), you may perform a mix of additions and multiplications. In particular, if you perform \(r\) operations as \(+2\) and the remaining \(k-r\) operations as \(\times2\), the resulting value is \((x+2r)\times2^{k-r}\). Hence, when \(x>0\) we have \[ f_{\max}(x,k)=\max_{0\le r\le k} \Bigl\{ (x+2r)\times2^{k-r} \Bigr\}. \]
  • If \(x \le 0\), the best option is to simply add 2 in every operation: \(f_{\max}(x,k)=x+2k\).
• For minimizing (\(f_{\min}(x,\ell)\)):
  • If \(\ell = 0\), then \(f_{\min}(x,0)=x\).
  • If \(x \ge 0\), a greedy strategy works: while \(\ell>0\),
    • If \(x \ge 5\) then use floor division: \(x \leftarrow \lfloor x/2 \rfloor\).
    • Otherwise, subtract 2: \(x \leftarrow x-2\).
  • If \(x < 0\), then at each operation:
    • If \(x < -2\), choose the operation that results in a smaller value: compare \(2\times x\) and \(x-2\); use the one that gives the lower result.
    • If \(x \ge -2\), simply subtract 2.

You must decide how to distribute the \(m\) operations between maximizing one element and minimizing another to achieve the maximum possible range.

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, where \(n\) is the number of elements in the sequence and \(m\) is the total number of operations.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output a single integer — the maximum possible range of the sequence after exactly \(m\) operations.

sample

3 1
1 2 3

5