文本是由单词组成的序列，而单词由字符组成。你的任务是将单词放入一个有 $W$ 列和足够多行的网格中。为了排版的美观，必须满足以下条件。

1. 文本中的单词必须保持其原始顺序。下图展示了一个包含 4 个单词的文本 “This is a pen” 排版到 11 列中的正确和错误示例。

图 I.1：一个好的排版。 图 I.2：错误 —— 不要改变单词的顺序。

1. 在同一行中相邻的两个单词之间，必须至少放置一个空格字符。为了满足其他条件，有时你必须放置多个空格。

图 I.3：错误 —— 单词之间必须用空格分隔。

1. 一个单词必须占用与其字符数相同数量的连续列。你不能通过换行或插入空格将一个单词拆分为两个或多个部分。

图 I.4：错误 —— 单个单词中的字符必须是连续的。

1. 文本必须左右对齐。也就是说，一行的第一个单词必须从该行的第一列开始，并且除了最后一行外，一行的最后一个单词必须在最后一列结束。

图 I.5：错误 —— 每行必须左右对齐。

当没有不必要的长空格时，文本的排版是最美观的。例如，图 I.6 中的排版最多包含 2 个连续空格，这比图 I.1 中包含 3 个连续空格的排版更美观。给定输入的文本和列数，请找到一种排版方案，使得单词之间最长连续空格的长度最小。

图 I.6：一个好且最美观的排版。

输入格式

输入包含多个数据集，每个数据集的格式如下：

$$W \quad N$$ $$x_1 \quad x_2 \quad \dots \quad x_N$$

$W$、$N$ 和 $x_i$ 均为整数。$W$ 是列数（$3 \le W \le 80,000$）。$N$ 是单词数（$2 \le N \le 50,000$）。$x_i$ 是第 $i$ 个单词的字符数（$1 \le x_i \le \frac{W-1}{2}$）。注意，$x_i$ 的上限保证了总是存在满足条件的排版方案。

最后一个数据集后面紧跟一行，包含两个零。

输出格式

对于每个数据集，输出单词之间最长连续空格长度的最小值。

样例

输入样例 1

11 4
4 2 1 3
5 7
1 1 1 2 2 1 2
11 7
3 1 3 1 3 3 4
100 3
30 30 39
30 3
2 5 3
0 0

输出样例 1

2
1
2
40
1