BN202606 魔法绳索

题目描述

魔法工坊中有 N 根绳索，第 i 根绳索的长度为 a_i。

现在，工匠需要从这些绳索中截取出至少 K 段长度相同的魔法绳。

每段魔法绳的长度必须是正整数，并且：

• 每根绳索可以被切成若干段；
• 不同绳索切出的绳段长度必须相同；
• 每根绳索剩余的部分可以丢弃；
• 不能把两根绳索拼接后再切割。

请你计算：每段魔法绳的长度最大是多少。

如果无法截取出至少 K 段长度相同的正整数绳段，输出 0。

输入格式

第一行包含两个正整数 N 和 K，分别表示绳索的数量和至少需要的魔法绳段数。

第二行包含 N 个正整数 a_1, a_2, ..., a_N，表示每根绳索的长度。

输出格式

输出一个整数，表示每段魔法绳的最大长度。

样例输入

4 7
10 15 20 8

样例输出

6

样例说明

当每段绳子的长度为 6 时：

• 长度为 10 的绳子可以截出 1 段；
• 长度为 15 的绳子可以截出 2 段；
• 长度为 20 的绳子可以截出 3 段；
• 长度为 8 的绳子可以截出 1 段。

一共可以截出：

1 + 2 + 3 + 1 = 7

段，满足至少 7 段的要求。

当每段长度为 7 时：

10 / 7 + 15 / 7 + 20 / 7 + 8 / 7
= 1 + 2 + 2 + 1
= 6

不足 7 段，因此答案是 6。

数据范围

• 1 ≤ N ≤ 10^5
• 1 ≤ K ≤ 10^14
• 1 ≤ a_i ≤ 10^9
• 保证所有 a_i 的总和不超过 10^14