Description

A lumber mill has $n$ logs. We want to cut them into $k$ segments, each of length $l$ (there may be leftover wood).

Of course, we want the segments to be as long as possible. Please find the maximum value of $l$.

The unit of length is $\text{cm}$. The lengths of the logs are positive integers, and we also require the lengths of the resulting segments to be positive integers.

For example, if there are two logs with lengths $11$ and $21$, and we need $6$ equal segments, the longest possible segment length is $5$.

Input Format

The first line contains two positive integers $n, k$, denoting the number of logs and the required number of segments.

The next $n$ lines each contain a positive integer $L_i$, the length of one log.

Output Format

A single line containing the maximum value of $l$.

If it is impossible to cut even segments of length $\text{1cm}$, output 0.

3 7
232
124
456

114

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le k \le 10^8$, $1 \le L_i \le 10^8$ ($i \in [1, n]$).

Translated by ChatGPT 5