Optimal Cow Allocation in Barn Construction

Farmer John is constructing a brand‐new, \(N\)-story barn with the help of his \(K\) cows. Each floor \(i\) requires \(a_i\) units of work. Every cow can complete 1 unit of work per hour, and each cow must be assigned to exactly one floor. Moreover, every floor must have at least 1 cow working on it.

If \(c_i\) cows are assigned to floor \(i\), then the work on that floor will finish in \(\frac{a_i}{c_i}\) hours. For safety reasons the floors must be built sequentially (i.e. floor \(i\) must be completed before construction on floor \(i+1\) can begin). Your task is to allocate the cows among the floors to minimize the total construction time:

[ T = \sum_{i=1}^{N} \frac{a_i}{c_i}, \quad\text{subject to } \sum_{i=1}^{N} c_i = K \text{ and } c_i \ge 1 \text{ (integer)}. ]

Output the minimum total time rounded to the nearest integer. It is guaranteed that the answer will differ from the rounding boundary by more than 0.1.

Constraints:

• \(1 \le N \le 10^5\)
• \(N \le K \le 10^{12}\)
• \(a_i\) are positive integers.

inputFormat

The first line contains two integers \(N\) and \(K\). The second line contains \(N\) integers, where the \(i\)th integer is \(a_i\), representing the work required on floor \(i\).

outputFormat

Output a single integer representing the minimum total construction time rounded to the nearest integer.

sample

3 4
10 1 1

7