Pădurar

Task

Nicholas works at a sawmill and needs to prepare a package of exactly $K$ identical planks, each having length $L$. The warehouse contains $N$ logs with lengths $H_1, H_2, \dots, H_N$.

Nicholas can cut several planks of length $L$ from a single log, but each cut wears out his saw. He has established the following rules:

1. One or more planks of length $L$ can be cut from any log. Any piece of wood remaining that is shorter than $L$ is considered waste.
2. Each cut consumes 1 unit of the saw's total durability $X$.
   • Example: If a log has length $10$ and planks of length $5$ are needed, one single cut is made in the middle to obtain $2$ planks (cost $1$ unit).
   • Example: If a log has length $12$ and planks of length $5$ are needed, two cuts are made (at distance $5$ and $10$) to obtain $2$ planks, the remaining $2$ being waste (cost $2$ units).

Help Nicholas find the maximum length $L$ that the $K$ planks can have, without exceeding the saw's durability $X$.

Input Data

The first line contains three integers $N, K$, and $X$.
The second line contains $N$ integers representing the log lengths $H_1, H_2, \dots, H_N$.

Output Data

Print a single natural number representing the maximum length $L$. If it is impossible to obtain $K$ planks, print $0$.

Constraints and Clarifications

• $1 \leq N \leq 100,000$
• $1 \leq K, X \leq 10^9$
• $1 \leq H_i \leq 10^9$
• For 20% of the score: $N, K, H_i \leq 100$
• For another 30% of the score: $N \leq 1,000, H_i \leq 10^6$

Example

padurar.in

2 4 3
10 12

padurar.out

5

Explanation

For $L=5$:

• From the first log ($10$), $2$ planks are obtained using $1$ cut.
• From the second log ($12$), $2$ planks are obtained using $2$ cuts.
  Total: $4$ planks and $3$ cuts. The conditions are met.
  If we chose $L=6$, we would obtain only $1 + 1 = 2$ planks, so $L=5$ is the maximum.