Minimum Divisor

You are given an array of integers A of size n and a positive integer threshold T. Your task is to find the minimum positive integer x such that:

$$\sum_{i=1}^{n}\lceil\frac{A_i}{x}\rceil \le T$$

Here, $$\lceil a \rceil$$ denotes the ceiling of a, which is the smallest integer greater than or equal to a.

You can assume that a solution always exists.

inputFormat

The input is read from standard input and consists of two lines:

• The first line contains two space-separated integers: n (the number of elements in the array) and T (the threshold).
• The second line contains n space-separated positive integers which represent the elements of the array A.

outputFormat

Output a single integer on standard output: the minimum positive integer x such that the sum of the ceilings of each array element divided by x does not exceed T.

4 6
1 2 5 9

5