题目描述

文章是一些单词组成的序列，单词由字母组成。你的任务是将一篇文章的单词填充到一个网格中，其中网格包含$W$列和足够多的行。为了布局之美，以下限制都需要满足。

1. 文章中的文字需要按照原有的顺序放置。
2. 在同一行的两个相邻单词之间要有至少一个空格。有时你会需要放置多于一个空格来满足其他限制。
3. 一个单词必须被放置到连续的列中，一个格子只含一个字符。你不能将通过增加空格或换行将一个单词分成多个部分。
4. 文章必须占据边缘两列的格子，即每行的第一个单词必须占用第一个格子，且除了最后一行之外的每行的最后一个单词必须占用最后一个格子。

文章拥有最美的布局时，每一行都不会有过多的连续空格，在下图的例子里只有最多2个连续空格，而第一个例子里有3个连续空格，所以下图的例子比第一个例子美观。给定文章的信息和列数，请你找到一个最优的布局，使得最长连续空格尽量短。

输入格式

输入包含多组测试数据。 每组数据第一行包含两个正整数 $W$ 和 $N$，其中 $W$ 表示列数$(3≤W≤80000)$，$N$表示文章的单词数量$(2≤N≤50000)$。 第二行包含$N$个正整数，按照文章中单词的顺序给出每个单词的字符数量， 对于第 $i$ 个单词的字符数量$x_i$，有$1≤x_i≤(W-1)/2$，从而这也使得答案一定存在。

输出格式

对于每组数据，输出一个正整数表示最长连续空格长度的最小值。

输入样例

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

输出样例

2
1
2
40
1

数据范围

对于 $100\%$ 的数据，坐标大于-500且小于500，半径大于0且小于500，光照强度大于0且小于80000。