TikTok Video Relevance Adjustment

Each operation chooses a positive rating and subtracts a fixed positive integer x from it. All ratings must be ≤0 after at most M operations; find the minimum x. The original example mixed in the process for a different array; for the given [4,3,2,7] with M=5, the correct answer is 4.

输入格式

The first line contains n M; the second line contains the ratings. 1≤n≤100000, 1≤rating≤10^9, n≤M≤10^9.

输出格式

Output a single integer, the answer.

样例 1

输入：

4 5
4 3 2 7

输出：

4

样例 2

输入：

3 6
1 2 3

输出：

1

样例 3

输入：

2 2
10 10

输出：

10

样例说明

The answers are 4, 1 and 10. In the first example x=3 needs 2+1+1+3=7 operations, while x=4 needs 1+1+1+2=5.