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:
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.
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$$$.
Print a single integer — the maximum length of the sequence of unmarked colors before Miss M selects the $$$(m+n)$$$-th color.
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.
1 111
11
1 311
5
1 511
2
1 1091033
15
3 11454034 5912 9134
22
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: