Inspired by her group's new song, Stella decides to treat her friends to dessert! They have a lineup of $$$n$$$ lemon cheesecakes, where the $$$i$$$th one has sweetness $$$a_i$$$. All the members plan to share the cheesecakes, but unfortunately Jiwoo despises sour tastes.
Luckily Stella has $$$k$$$ spoonfuls of syrup, which she can apply to the cheesecakes as she wishes. For instance, she could choose to use all the syrup on a single cheesecake, or disperse such that each cake gets one spoon. Adding a spoon of syrup increases a cake's sweetness by $$$+1$$$. Jiwoo's score for the lineup is the smallest sweetness across all the cheesecakes.
Can you help Stella maximize Jiwoo's score?
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n,k \le 2 \cdot 10^5$$$), denoting the number of cheesecakes and the number of spoons of syrup.
The second line contains $$$n$$$ space-separated integers representing the array $$$a$$$, where $$$a_i$$$ denotes the sweetness of the $$$i$$$th cake ($$$1 \le a_i \le 10^9$$$).
Output a single integer, denoting the maximum value for $$$\min_i a_i$$$ after using the syrup optimally.
4 53 1 4 2
3
In the sample, it is possible to transform $$$[3, 1, 4, 2]$$$ to $$$[4, 4, 4, 3]$$$, which gives a minimum value of $$$3$$$. It can be shown it is not possible to do better.
It may help to listen to the following song: https://open.spotify.com/track/0NGFAcYQVHCIdQea2qSs1I?si=fdd91b739c0c4549
