题目描述

给定一个由正整数组成的序列$A=(A_1, A_2, \ldots, A_N)$和一个正整数$X$。你可以执行以下操作任意次数（可能为零）：

• 选择一个索引$i$（$1\leq i\leq N$）和一个非负整数$x$，满足$0\leq x\leq X$。将$A_i$更改为$2A_i+x$。

在执行这些操作后，找出$\\max\{A_1,A_2,\ldots,A_N\}-\\min\{A_1,A_2,\ldots,A_N\}$的最小可能值。

约束条件

• $2\leq N\leq 10^5$
• $1\leq X\leq 10^9$
• $1\leq A_i\leq 10^9$

输入

输入以以下格式从标准输入给出：

$N$ $X$ $A_1$ $A_2$ $\ldots$ $A_N$

输出

打印在执行操作后，$\\max\{A_1,A_2,\ldots,A_N\}-\\min\{A_1,A_2,\ldots,A_N\}$的最小可能值。

示例输入1

4 2
5 8 12 20

示例输出1

6

假设$(i, x)$表示将$A_i$更改为$2A_i+x$的操作。以下是一种最优的操作序列：

• $(1,0)$，$(1,1)$，$(2,2)$，$(3,0)$

这样得到的$A=(21, 18, 24, 20)$，从而$\\max\{A_1,A_2,A_3,A_4\}-\\min\{A_1,A_2,A_3,A_4\} = 6$。

示例输入2

4 5
24 25 26 27

示例输出2

0

以下是一种最优的操作序列：

• $(1,5)$，$(1,5)$，$(2,5)$，$(2,1)$，$(3,2)$，$(3,3)$，$(4,0)$，$(4,3)$

这样得到的$A=(111,111,111,111)$，从而$\\max\{A_1,A_2,A_3,A_4\}-\\min\{A_1,A_2,A_3,A_4\} = 0$。

示例输入3

4 1
24 25 26 27

示例输出3

3

不进行任何操作，$\\max\{A_1,A_2,A_3,A_4\}-\\min\{A_1,A_2,A_3,A_4\} = 3$。

示例输入4

10 5
39 23 3 7 16 19 40 16 33 6

示例输出4

13