Contest Duration: - (local time) (180 minutes) Back to Home
B - 2A + x /

Time Limit: 4 sec / Memory Limit: 1024 MB

### 問題文

• 添字 i1\leq i\leq N）および、0\leq x\leq X となる非負整数 x を選ぶ。A_i2A_i+x に変更する。

### 制約

• 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


### 入力例 1

4 2
5 8 12 20


### 出力例 1

6


A_i2A_i+x に変更する操作を (i, x) と表すことにします。最適な操作列の一例は次の通りです。

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

### 入力例 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)

### 入力例 3

4 1
24 25 26 27


### 出力例 3

3


### 入力例 4

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


### 出力例 4

13


Score : 700 points

### Problem Statement

You are given a sequence A = (A_1, A_2, \ldots, A_N) of positive integers and a positive integer X. You can perform the operation below any number of times, possibly zero:

• Choose an index i (1\leq i\leq N) and a non-negative integer x such that 0\leq x\leq X. Change A_i to 2A_i+x.

Find the smallest possible value of \max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\} after your operations.

### Constraints

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

### Input

Input is given from Standard Input in the following format:

N X
A_1 A_2 \ldots A_N


### Output

Print the smallest possible value of \max\{A_1,A_2,\ldots,A_N\}-\min\{A_1,A_2,\ldots,A_N\} after your operations.

### Sample Input 1

4 2
5 8 12 20


### Sample Output 1

6


Let (i, x) denote an operation that changes A_i to 2A_i+x. An optimal sequence of operations is

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

which yields A = (21, 18, 24, 20), achieving \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 6.

### Sample Input 2

4 5
24 25 26 27


### Sample Output 2

0


An optimal sequence of operations is

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

which yields A = (111,111,111,111), achieving \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 0.

### Sample Input 3

4 1
24 25 26 27


### Sample Output 3

3


Performing no operations achieves \max\{A_1,A_2,A_3,A_4\}-\min\{A_1,A_2,A_3,A_4\} = 3.

### Sample Input 4

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


### Sample Output 4

13