Churro 是一只胖乎乎且精力充沛的豚鼠，它刚刚在一家名为 Jaime's Palace 的高档餐厅开始了一份新工作。作为最新入职的员工，它只负责洗盘子和整理盘子。Churro 发现，保持盘子整洁且方便厨师拿取的最有效方法是将它们存放在一个单栈中。

Jaime's Palace 共有 $P$ 个盘子，在第 $i$ 天会使用其中的 $K_i$ 个。Churro 设计了一套严密且极具逻辑性的盘子管理系统。在第 $i$ 天，它从栈顶取出 $K_i$ 个盘子，厨师在当天会把每个盘子刚好使用一次。在一天结束时，Churro 清洗这 $K_i$ 个用过的盘子，并以任意顺序将它们放回栈顶。

Churro 的系统非常成功。然而，它对以下问题感到好奇：在重复上述步骤 $D$ 天后，它能否确定存在一个盘子，其被使用的次数至少为 $t$ 次？它能保证的 $t$ 的最大值是多少？请帮助 Churro 确定这个值。

输入格式

第一行包含两个整数 $P$ ($2 \le P \le 2000$) 和 $D$ ($1 \le D \le 2000$)，分别表示盘子的数量和天数。

第二行包含 $D$ 个整数 $K_1, K_2, \dots, K_D$ ($1 \le K_i \le P$，对于 $i = 1, 2, \dots, D$)，其中 $K_i$ 是第 $i$ 天使用的盘子数量。

输出格式

输出一行，包含一个整数，表示 $t$ 的最大值，使得在 $D$ 天后，无论每天结束时放回栈顶的盘子如何重新排序，都至少有一个盘子被使用了至少 $t$ 次。

样例

输入样例 1

10 3
1 1 2

输出样例 1

3

样例 1 说明

在前两天中，Churro 每天都从栈顶取出一个盘子并将其放回栈顶，因此该盘子被使用了两次。在第三天，它取出栈顶的两个盘子，因此无论第三天结束时盘子以何种顺序放回栈顶，这两个盘子中都必定有一个被使用了三次。

输入样例 2

10 4
5 3 5 2

输出样例 2

3