#4757. [Usaco2017 Jan]Building a Tall Barn

题目描述

Farmer John is building a brand new, N-story barn, with the help of his KK cows (1≤N≤K≤1012 and N

≤10^5). To build it as quickly as possible, he needs your help to figure out how to allocate work a

mong the cows.Each cow must be assigned to work on exactly one specific floor out of the N total flo

ors in the barn, and each floor must have at least one cow assigned to it. The iith floor requires a

iai units of total work, and each cow completes one unit of work per hour, so if cc cows work on flo

or i, it will be completed in ai/c units of time. For safety reasons, floor ii must be completed bef

ore construction can begin on floor i+1Please compute the minimum total time in which the barn can b

e completed, if the cows are allocated to work on floors in an optimal fashion. Output this number r

ounded to the nearest integer; it is guaranteed that the solution will be more than 0.1 from the bou

ndary between two integers.

给定长度为N的序列ai，对每个ai分配ci使得ci>0(ci为整数)且ci之和等于K，求出最小的ai/ci之和

输入格式

The first line of input contains N and K.

The next N lines contain a1…aN, each a positive integer of size at most 1012

输出格式

Please output the minimum time required to build the barn, rounded to the nearest integer.

样例

样例输入

2 5  

10  

4

样例输出

5

数据范围与提示