Choose Colors
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 \leq n \leq 100$$$, $$$1 \leq m \leq 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 \leq a_i \leq 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.

Scoring

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

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

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

Examples

Input
1 1
11
Output
11
Input
1 3
11
Output
5
Input
1 5
11
Output
2
Input
1 109
1033
Output
15
Input
3 1145
4034 5912 9134
Output
22

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.