← 返回题目列表

Codeforces · 830/C

C. 竹隔断

中文机器翻译题面 查看原题

弗拉基米尔想要对他办公室的隔断进行现代化改造。为了让办公室更舒适,他决定拆除隔断,并连续种植几根竹子。他认为如果有n根竹子排成一排就好了,从左边算起第i根竹子有ai米高。

Vladimir 刚刚连续种植了 n 根竹子,每根竹子现在的高度为 0 米,但它们每天都会长高 1 米。为了让隔断美观,弗拉基米尔可以在任意高度(不大于竹子的高度)将每根竹子砍一次,然后竹子就会停止生长。

Vladimir 希望每隔 d 天检查一次竹子(即种植后 d 天,然后是 2d 天后,依此类推),并砍伐达到所需高度的竹子。弗拉基米尔希望他要砍掉的竹子部分的总长度不超过 k 米。

他可以选择的最大值 d 是多少,这样他就可以在不砍掉超过 k 米的竹子的情况下实现他想要的目标?

输入

第一行包含两个整数 n 和 k (1 ≤ n ≤ 100, 1 ≤ k ≤ 1011)——竹子的数量和切割部分的最大总长度,以米为单位。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) – 所需的竹子高度,单位为米。

输出

打印一个整数 - d 的最大值,这样弗拉基米尔就可以达到他的目标。

示例

输入 #1

3 4
1 3 5

输出 #1

3

输入 #2

3 40
10 30 50

输出 #2

32

注意

在第一个示例中,Vladimir 可以每 3 天检查一次竹子。三天后,他会砍第一根和第二根竹子,六天后,他会砍第三根竹子。切割部分的总长度为2+0+1=3米。