Xây chuồng cao tầng

Bác nông dân John đang xây một chuồng bò gồm $N$ tầng, với sự giúp đỡ của $K$ con bò. Mỗi con bò phải được phân công vào đúng một tầng, và mỗi tầng phải có ít nhất một con bò.

Tầng thứ $i$ cần $a_i$ đơn vị công việc để hoàn thành. Nếu có $c$ con bò được phân công vào tầng $i$, thời gian để hoàn thành tầng đó là $a_i/c$ giờ.

Các tầng phải được xây tuần tự (tầng $i$ phải xong trước khi bắt đầu tầng $i+1$), nên tổng thời gian là tổng thời gian hoàn thành từng tầng.

Hãy xác định tổng thời gian tối thiểu để xây xong chuồng bò, với cách phân bổ bò tối ưu.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $N$ và $K$.
• $N$ dòng tiếp theo, dòng thứ $i$ chứa giá trị $a_i$.

Dữ liệu ra

In ra tổng thời gian tối thiểu, làm tròn đến số nguyên gần nhất.

Dữ liệu đầu vào được đảm bảo rằng đáp án cách giá trị nguyên gần nhất hơn $0.1$.

Ràng buộc

• $1\le N\le K\le {10}^{12}$
• $N\le {10}^5$
• $1\le a_i\le {10}^{12}$

Ví dụ

Ghi chú

Lưu ý rằng $K$ có thể rất lớn (đến ${10}^{12}$), nên thuật toán tham lam thông thường (thêm từng bò một) sẽ không đủ nhanh.