B. Lemon Tang (Korean Ver.)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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?

Input

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

Output a single integer, denoting the maximum value for $$$\min_i a_i$$$ after using the syrup optimally.

Example
Input
4 5
3 1 4 2
Output
3
Note

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