题目描述

小 $H$ 正在学习四则运算，为了验证他的学习成果，小林老师给出一个长为 $n$ 整数序列 $a_i$。并让小 $H$ 给这个序列进行 $m$ 次操作。

每次操作可以任意选择序列中一个数 $a_i$，令 $a_i$ 变成 $a_i+2$，$a_i-2$，$a_i\times 2$，$\frac{a_i}{2}$ 这四个结果中的一个。

老师希望 $m$ 次操作后，整个序列的极差（最大值减最小值）最大。

显然 小 $H$ 没有认真学习，所以他希望你来帮他回答这个问题。

输入格式

第一行两个整数 $n$，$m$。

第二行 $n$ 个整数，表示序列 $a_i$。

输出格式

共一行一个整数，表示最大的极差。

3 2
0 1 0

6

3 2
0 -1 0

6

提示

样例1解释

第一步操作：将 $1$ 加上 $2$ 得到 $3$。

第二步操作：将 $3$ 乘以 $2$ 得到 $6$。

极差为 $6-0=6$。

样例2解释

第一步操作：将 $-1$ 减去 $2$ 得到 $-3$。

第二步操作：将 $-3$ 乘以 $2$ 得到 $-6$。

极差为 $0-(-6)=6$。

数据范围

对于 $40\%$ 的数据，$2 \le n \le 5$，$1\le m \le5$。

对于 $100\%$ 的数据，$2 \le n \le 10^6$，$1 \le m \le 10$，$-10^9 \le a_i \le 10^9$。