Logs

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

There are $N$ logs of lengths $A_i$. Perform at most $K$ cuts at arbitrary real positions. Minimize the length of the longest resulting log and print the ceiling of that optimum.

Input

The first line contains $N,K$. The second line contains $A_1,\ldots,A_N$.

Output

Print the required integer.

Subtasks

• Subtask 1 — 20%: $N\le100$.
• Subtask 2 — 30%: $N\le5000$.
• Subtask 3 — 50%: $N\le2\cdot10^5$, $K\le10^9$, $A_i\le10^9$.

Example

Input

2 3
7 9

Output

4

Explanation

The optimal longest piece has length 3.5, whose ceiling is 4.