Cắt khúc gỗ (Logs)

Nguồn: AtCoder

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $N$ khúc gỗ, độ dài lần lượt là $A_1,A_2,\ldots,A_N$. Ta được thực hiện nhiều nhất $K$ lần cắt. Mỗi lần chọn một khúc gỗ dài $L$ và cắt tại vị trí thực $t$ với $0<t<L$, tạo ra hai khúc dài $t$ và $L-t$.

Sau khi cắt, xét độ dài của khúc dài nhất. Hãy làm giá trị này nhỏ nhất có thể rồi làm tròn lên số nguyên và in kết quả.

Input

Dòng đầu chứa $N,K$. Dòng thứ hai chứa $A_1,\ldots,A_N$.

Output

In số nguyên cần tìm.

Subtask

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

Ví dụ

Input

2 3
7 9

Output

4

Giải thích

Có thể cắt khúc $7$ thành $3.5+3.5$ và khúc $9$ thành ba đoạn dài không quá $3.5$. Độ dài lớn nhất tối ưu là $3.5$, làm tròn lên được $4$.