Beautiful Layout

A text is made up of words, and each word is made up of letters. You want to write the text onto manuscript paper that has $W$ columns per row. The number of rows is unlimited.

When writing the text, the following rules are always obeyed.

1. The order of the words must not be changed.
2. On the same row, there must be at least one blank cell between two neighboring words.
3. A word occupies as many consecutive cells as it has letters. A word cannot be split across two rows, and no blank cell may appear inside a word.
4. The text must be justified against both the left and right edges. That is, the first word of every row starts in the first column, and the last word of every row except the last row must end in column $W$.

The smaller the longest run of consecutive blank cells in a placement, the nicer the text looks. A placement that makes the longest run of consecutive blank cells as small as possible is called a beautiful layout. Blank cells left after the last word of the final row are not counted.

For example, four words of lengths $4, 2, 1, 3$ (such as "This is a pen") written onto $11$-column paper according to the rules can be arranged so that the longest run of consecutive blank cells is as small as $2$. In contrast, another rule-obeying arrangement of the same four words can have a longest blank run of $3$, which is not beautiful.

Given the length of each word and the number of columns $W$, write a program that finds the longest run of consecutive blank cells in a beautiful layout.

The input consists of several test cases.

The first line of each test case contains two integers $W$ and $N$, where $W$ is the number of columns of the manuscript paper and $N$ is the number of words. ($3 \le W \le 80000$, $2 \le N \le 50000$)

The second line contains $N$ integers $x_1, x_2, \dots, x_N$, where $x_i$ is the length of the $i$-th word. ($1 \le x_i \le (W-1)/2$)

It is guaranteed that a placement satisfying the rules always exists.

The last line of the input contains two zeros; this line is not processed.

For each test case, print the longest run of consecutive blank cells in a beautiful layout, one value per line.