3700 - 切木头
Description

有 n 根木棍,长度不等。现在要把它们切成同等长度的木棍 m 根,并且每段的长度都为整数。问这 m 根木棍最长能有多长?如果分不出来,输出 0。

Input

第一行两个数 n, m,中间用空格分隔 (1 <= n <= 100000, 1 <= m <= 10^9)。
后面 n 行,每行一个数,对应木棍的长度 (1 <= Li <= 10^9)。

Output

输出一个整数,对应木棍的长度。

Examples

Input

3 10
15
25
12

Output

5
Hint

切出的段数随每段长度单调递减。二分最终长度 x,判断按 x 一共能切出多少根(sum of Li/x)是否不少于 m。

Source
51nod 2655
Tags
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1