# 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.

Sample Input 1 | Sample Output 1 |
---|---|

7 5 1 2 3 4 5 3 1 |
19 |

Sample Input 2 | Sample Output 2 |
---|---|

8 3 0 99 3 2 2 2 2 2 |
23 |

Sample Input 3 | Sample Output 3 |
---|---|

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