Choose Colors

Miss M not only enjoys inventing interesting legends for programming problems but also loves painting, especially using harmonious color combinations, such as complementary colors from the color wheel. However, this time she decided to choose colors for her painting differently.

Miss M took $n$ color wheels (you can look at the note section to see what a color wheel is), each with different shades consisting of $(a_i+1)$ colors, and has already selected one initial color on each wheel, marking it as used. Then, she will choose each subsequent color using the following algorithm:

1. Find the longest sequence among all the color wheels of unmarked colors; if there are several, choose any.

2. If the length of such a sequence is odd, take the color exactly in the middle and mark it as used.

3. If the length of such a sequence is even, take one of the two middle colors and mark it as used.

Miss M wants to choose $m$ more colors, and she is also interested in what the maximum length of the sequence of unmarked colors will be before she selects the $(m+n)$-th color.

Input

The first line contains two integers $n$ and $m$ ($1\le n\le 100$, $1\le m\le 10^{18}$) — the number of color wheels and the number of colors Miss M wants to take additionally (i.e., not counting the first marked colors on each wheel).

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^{18}$).

It is guaranteed that $m$ is no more than the sum of all $a_i$.

Output

Print a single integer — the maximum length of the sequence of unmarked colors before Miss M selects the $(m+n)$-th color.

Examples

Note

Explanation for the second example: We are given one color wheel containing $12$ colors. Miss M has already chosen one color from the wheel (marked as number $1$ in the picture). Now she wants to choose $3$ more colors. Therefore, the sequence of her actions is as follows:

1. The maximum length of the sequence of unmarked colors is $11$. Therefore, we choose the color that will be in the middle and mark it with the number $2$.

2. Now we have sequences of $5$ and $5$ unmarked colors; we choose any and in the middle of the sequence, we select a color and mark it with the number $3$.

3. Among the sequences — $2$, $2$, and $5$ we choose $5$ — this is the maximum length of the sequence of unmarked colors before Miss M selects the $4$-th color.

The color wheel from the second example in the problem statement.

Scoring

If your solution works correctly for $n=1$ and $a_1\le 100$, it will score at least $25$ points.

If your solution works correctly for $n=1$ and $a_1\le 10^6$, it will score at least $50$ points.

If your solution works correctly for $n=1$, it will score at least $75$ points.