Problem F
Compression

You have a list $x_1,\dots ,x_ N$ of natural numbers and would like to encode it in a particular compressed format while minimizing the size of the compressed file. The compressed format consists of a string of bits (0 or 1), which is divided into contiguous blocks of variable length. Each block encodes a subarray $x_ i,\dots ,x_ j$ of $x_1,\dots ,x_ N$, and when concatenated, the blocks encode the full list.

The encoding of each block consists of a header and some data. The header stores three parameters: a bit size $s$, a block size $k$, and a mode $m$, using $c$ bits in total. You do not need to be concerned with how these values are encoded, just that the header takes $c$ bits. It is required that $0\le s\le 30$, $1\le k\le N$, and $m\in \{ 1,2\} $. The original subarray $x_ i,\dots ,x_{i+k-1}$ for the block can be decompressed from the block data as follows. The block data elements $y_ i,\dots ,y_{i+k-1}$ are always encoded using $s$ bits each, but how they are encoded depends on the mode $m$. In mode $1$, the block data exactly encodes the original subarray, i.e., $x_ j=y_ j$ for $j=i,\dots ,i+k-1$. In this case we must have $0\le y_ j<2^ s$ because the elements $y_ j$ need to fit in $s$ bits each. In mode $2$, the block data encodes a signed offset from the previous original data element, i.e., $x_ j=x_{j-1}+y_ j$ for $j=i,\dots ,i+k-1$. In this case the $y_ j$ are stored in $s$-bit two’s complement form, so we must have $-2^{s-1}\le y_ j<2^{s-1}$. For the purposes of decoding the first block, is assumed that $x_0=0$.

So, a block with parameters $s$, $k$, and $m$ requires $c+s\cdot k$ bits in total. By carefully choosing the number of blocks and the values $s$, $k$, and $m$ for each block, you can minimize the number of bits needed to store the list in this compressed format.

Input

The first line contains two integers, $N$ and $c$, with $1\le N\le 10^5$ and $0\le c\le 10^3$. The next $N$ lines contain integers $x_1\dots ,x_ N$, with $0\le x_ i\le 10^9$.

Output

Output the minimum number of bits needed to encode $x_1,\dots ,x_ N$ in the specified format.

Explanation

In Sample Input $3$, the optimal compression splits the data into three blocks. First, $0,1,3,6,10,15,21,28$ is encoded using mode $2$ with a bit size of $4$ into the block data $0,1,2,3,4,5,6,7$, which uses $16+4\cdot 8=48$ bits. The second block encodes the next $7$ numbers, $1\, 036,0,1\, 035,1,1\, 034,2,1\, 033$ using mode $1$ with a bit size of $11$ (since $1\, 036<2^{11}$), which uses $16+11\cdot 7=93$ bits. The final block encodes the numbers $1\, 045,1\, 055,1\, 066,1\, 078,1\, 060,1\, 091$ using mode $2$ and a bit size of $6$ into the block data $12,10,11,12,-18,31$, which uses $16+6\cdot 6=52$ bits. The three blocks use a total of $48+93+52=193$ bits.

7 5
1
2
3
4
5
3
1

19

8 3
0
99
3
2
2
2
2
2

23

21 16
0
1
3
6
10
15
21
28
1036
0
1035
1
1034
2
1033
1045
1055
1066
1078
1060
1091

193