题目描述

露营过程中希蒙他们开始了吃烧烤，这次烧烤一共有 M 种食物。希蒙需要把所有的烧烤分给 N 个孩子。每个孩子得到的所有烧烤都必须是相同的食物，而且可以有一些孩子一串烧烤也没得到。

我们把愤怒值定义为分给一个孩子最多的烧烤数量。请你帮助希蒙分烧烤，使得愤怒值最小。

例如，如果有 4 个鸡腿 和 7 个鸡翅，要分给 5 个孩子，

那么我们可以这样划分：|鸡腿*2|鸡腿*2|鸡翅*2|鸡翅*2|鸡翅*3|。

这样分的愤怒值为 3，是最小的。

注意：所有的烧烤必须分完

输入格式

输入共 M+1 行。

第一行包含两个正整数 N,M，分别表示孩子数和烧烤的种类数。

接下来 M 行的第 i 行包含一个正整数 $x（x \in [1,10^9]$，表示有 x 个种类为 i 的烧烤。

输出格式

输出一行一个整数，表示最小的愤怒值。

样例

输入样例1

5 2
7
4

输出样例1

3

输入样例2

7 5
7
1
7
4
4

输出样例2

4

数据范围与提示

对于 $100\%$ 的数据，保证 $1 \le M \le 3 \times 10^5$ ，$1 \le N \le 10^9，M \le N$。