Wood Processing

Problem Description

To protect the environment, the lumber yard has $n$ logs and now wants to cut these logs into $k$ pieces of length $l$ each; there may be leftover material after cutting.

We want the resulting pieces to be as long as possible; find the maximum value of $l$.

Lengths are measured in $\text{cm}$; the logs have positive-integer lengths, and we require the cut pieces to have positive-integer lengths as well.

For example, given two logs of lengths $11$ and $21$, to be cut into $6$ equal pieces, the longest possible piece length is clearly $5$.

Input Format

The first line contains two positive integers $n,k$: the number of logs and the number of pieces needed.

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

Output Format

One line: the maximum value of $l$.

If even a $1\text{ cm}$-long piece cannot be cut, output $0$.

Sample Input

3 7
232
124
456

Sample Output

114

Sample Explanation

For the first sample, the three logs have lengths $232$, $124$, $456$ and we need to cut out $7$ equal pieces. When the piece length is $114$, the first log yields $2$ pieces, the second yields $1$ piece, and the third yields $4$ pieces, for a total of $2+1+4=7$ pieces, which exactly meets the requirement. If the length increases to $115$, at most $2+1+3=6$ pieces can be cut, which is fewer than $7$, so the maximum length is $114$.

Constraints

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