Choose Colors#245
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 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:
Find the longest sequence among all the color wheels of unmarked colors; if there are several, choose any.
If the length of such a sequence is odd, take the color exactly in the middle and mark it as used.
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 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.
The first line contains two integers and (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 integers a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^{18}).
It is guaranteed that is no more than the sum of all a_i.
Print a single integer — the maximum length of the sequence of unmarked colors before Miss M selects the (m+n)-th color.
Example
Example 1
Example 2
Example 3
Example 4
Explanation for the second example: We are given one color wheel containing colors. Miss M has already chosen one color from the wheel (marked as number in the picture). Now she wants to choose more colors. Therefore, the sequence of her actions is as follows:
The maximum length of the sequence of unmarked colors is . Therefore, we choose the color that will be in the middle and mark it with the number .
Now we have sequences of and unmarked colors; we choose any and in the middle of the sequence, we select a color and mark it with the number .
Among the sequences — , , and we choose — this is the maximum length of the sequence of unmarked colors before Miss M selects the -th color.
The color wheel from the second example in the problem statement.
If your solution works correctly for n=1 and a_1 \leq 100, it will score at least points.
If your solution works correctly for n=1 and a_1 \leq 10^6, it will score at least points.
If your solution works correctly for n=1, it will score at least points.