You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

春天到了，春姑娘给北辰OI俱乐部带来了很多鲜花，每朵鲜花只有一种颜色，总共有 $M$ 种不同的颜色。

于老师决定将这些鲜花分发给 $N$ 个表现好的孩子，每个孩子获得的所有鲜花都必须是相同的颜色。允许表现不好的孩子一朵鲜花都没有，但所有的鲜花都必须被发给某个孩子。

我们定义 北辰OI劳模差异值 为获得鲜花最多的孩子所得鲜花的数量。请你帮助于老师合理分发鲜花，使得北辰OI劳模差异值最小。

例如，将 $4$ 朵红色鲜花（$\texttt{RRRR}$）和 $7$ 朵蓝色鲜花（$\texttt{BBBBBBB}$）分给 $5$ 个孩子，那么分配方案 $\texttt{RR}$，$\texttt{RR}$，$\texttt{BB}$，$\texttt{BB}$，$\texttt{BBB}$ 的北辰OI劳模差异值 $3$ 最小。

输入格式

第一行两个正整数，$N,M$，含义如题目所示。

第二行 $M$ 个整数，表示第 $M$ 个颜色的鲜花有几朵，题目保证每种颜色的鲜花的数量都在 $[1,10^9]$ 中。

输出格式

一行一个整数，表示最小的北辰OI劳模差异值。

样例

样例输入 1

7 4
1 2 3 4

样例输出 1

2

数据范围

对于 $20\%$ 的数据，保证 $1 \le M \le 10$。

对于另外 $30\%$ 的数据，保证 $1\le M\le 1000$，$1\le N\le 10000$。

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