Farmer John đang xây một chuồng bò hoàn toàn mới gồm \(N\) tầng với sự giúp đỡ của \(K\) con bò (\(1 \leq N \leq K \leq 10^{12}\) và \(N \leq 10^5\)). Để xây xong nhanh nhất có thể, ông cần bạn giúp phân bổ công việc cho đàn bò.

Mỗi con bò phải được phân công làm việc ở đúng một tầng cụ thể trong tổng số \(N\) tầng của chuồng, và mỗi tầng phải có ít nhất một con bò được phân công. Tầng thứ \(i\) cần tổng cộng \(a_i\) đơn vị công việc, và mỗi con bò hoàn thành một đơn vị công việc mỗi giờ; do đó, nếu có \(c\) con bò làm việc ở tầng \(i\), tầng này sẽ hoàn thành sau \(a_i/c\) đơn vị thời gian. Vì lý do an toàn, tầng \(i\) phải được hoàn thành trước khi có thể bắt đầu xây tầng \(i+1\).

Hãy tính tổng thời gian nhỏ nhất để hoàn thành chuồng khi đàn bò được phân bổ giữa các tầng một cách tối ưu. In số này sau khi làm tròn đến số nguyên gần nhất; đảm bảo rằng nghiệm cách ranh giới làm tròn giữa hai số nguyên hơn \(0.1\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\).

\(N\) dòng tiếp theo chứa \(a_1 \ldots a_N\), mỗi giá trị là một số nguyên dương không quá \(10^{12}\).

Dữ liệu ra

In thời gian nhỏ nhất cần để xây xong chuồng, được làm tròn đến số nguyên gần nhất.

Ví dụ

2 5
10
4

5

Nguồn

USACO 2017 January Contest, Platinum — Building a Tall Barn. Tác giả đề: Yang Liu.

https://usaco.org/index.php?page=viewproblem2&cpid=697