一家弹珠工厂向一家幼儿园捐赠了一大箱弹珠。每个弹珠都有 $M$ 种不同颜色中的一种。老师需要将所有的弹珠分给班上的 $N$ 个孩子。

有些孩子可以分不到任何弹珠。但是，没有孩子想要不同颜色的弹珠——换句话说，每个孩子分到的所有弹珠必须是同一种颜色的。

老师也知道，如果某个孩子分到了太多的弹珠，其他孩子就会嫉妒。作为一种近似，我们将班级中的嫉妒值定义为分给单个孩子的弹珠数量的最大值。请帮助老师分配弹珠，以使嫉妒值最小。

例如，如果箱子里有 4 个红弹珠（RRRR）和 7 个蓝弹珠（BBBBBBB），我们需要将它们分给 5 个孩子，我们可以通过以下方式分配来达到嫉妒值为 3 的效果：RR、RR、BB、BB、BBB。这是可以达到的最小嫉妒值。

输入格式

输入的第一行包含两个正整数 $N$（$1 \le N \le 10^9$），表示孩子的数量，和 $M$（$1 \le M \le 300\,000$，$M \le N$），表示不同颜色的数量。

接下来的 $M$ 行，每行包含一个范围在 $[1, 10^9]$ 内的正整数，其中第 $K$ 行的整数表示颜色为 $K$ 的弹珠数量。

输出格式

输出的第一行也是唯一的一行，应当包含最小可能的嫉妒值。

样例

输入样例 1

5 2
7
4

输出样例 1

3

输入样例 2

7 5
7
1
7
4
4

输出样例 2

4