弗拉基米尔想要对他办公室的隔断进行现代化改造。为了让办公室更舒适,他决定拆除隔断,并连续种植几根竹子。他认为如果有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米。