E. Enthusiast of Algorithms
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In this Summer holiday, Bob has participated in the recent Codeforces round and it was his very first online programming contest experience! By ranking the $$$7156^{th}$$$, Bob successfully got the title Newbie and became a grey contestant in Codeforces. Glancing through the final standing, Bob saw a group of Legendary Grandmasters solving all the problems with incredible speed. He realized that there are still a lot of hard work for him to become one of them in the future.

Motivated by the outstanding results of top programmers, Bob decided to start with learning more algorithms. Yesterday, he borrowed an Algorithm Book in the library. Inside the book, algorithms are categorized into $$$N$$$ categories, such as Graph, String, etc. In the $$$i^{th}$$$ category, there are $$$a_i$$$ different algorithms. There are only $$$K$$$ days left in the Summer holiday! Bob is going to learn exactly $$$M$$$ algorithms each day in the following $$$K$$$ days. For the sake of consistency, the $$$M$$$ algorithms learnt in each day should be belonging to the same category.

Bob really wants to become a Legendary Grandmaster, he seeks your help in deciding the number of algorithms to learn each day. Therefore, your job is to find the maximum value $$$M$$$, such that Bob will be learn exactly $$$M$$$ different new algorithms under the same category each day in the following $$$K$$$ days. Note that it is possible to have some algorithms missed out in Bob's learning process as the time remaining is limited in the Summer holiday.

Input

The first line of the input contains two integers $$$N$$$ ($$$1 \leq N \leq 10^5$$$) and $$$K$$$ ($$$1 \leq K \leq 10^5$$$), denoting the number of categories and the number of days remaining in the Summer holiday respectively.

The second line of the input contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$1 \leq a_i \leq 10^5$$$) each separated by a space, where $$$a_i$$$ represents the number of different algorithms under category $$$i$$$.

It is guaranteed that $$$\sum_{i = 1} ^ {N} a_i \geq K$$$.

Output

The first and the only line of the output should contain a single integer $$$M$$$ representing the maximum number of different new algorithms Bob can learn each day in the remaining days of the Summer holiday.

Example
Input
5 5
4 6 7 3 1
Output
3
Note

Bob can learn 3 algorithms under category 1 on day 1. 3 algorithms under category 2 on each of day 2 and 3. 3 algorithms under category 3 on each of day 4 and 5. It can be proven that 3 is the maximum number of algorithms for Bob to learn each day.