Cắt dây (Ropes)

Nguồn: Codeforces

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

Đề bài

Có $n$ sợi dây, sợi thứ $i$ dài $a_i$. Có thể cắt các sợi dây thành nhiều đoạn và bỏ phần thừa.

Hãy tìm độ dài thực lớn nhất $x$ sao cho có thể thu được ít nhất $k$ đoạn dây, mỗi đoạn có độ dài đúng bằng $x$.

Input

Dòng đầu chứa $n,k$. $n$ dòng tiếp theo chứa độ dài $a_i$.

Output

In độ dài lớn nhất. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá $10^{-6}$.

Subtask

• Subtask 1 — 20%: $n=1$.
• Subtask 2 — 30%: $1\le n,k\le1000$.
• Subtask 3 — 50%: $1\le n,k\le10^4$, $1\le a_i\le10^7$.

Ví dụ

Input

4 11
802
743
457
539

Output

200.5000000000

Giải thích

Với độ dài $200.5$, số đoạn lấy được là $4+3+2+2=11$. Tăng thêm một lượng đủ lớn sẽ làm số đoạn giảm xuống dưới $11$.