아름다운 레이아웃

글은 여러 개의 단어로 이루어져 있고, 각 단어는 글자들로 이루어져 있다. 이 글을 가로 $W$칸짜리 원고지에 써넣으려 한다. 원고지의 행(줄)의 개수에는 제한이 없다.

원고지에 글을 쓸 때 항상 다음 규칙을 지킨다.

1. 단어의 순서를 바꾸지 않는다.
2. 같은 줄에서 이웃한 두 단어 사이에는 빈칸이 적어도 한 칸 있어야 한다.
3. 한 단어는 그 글자 수만큼 연속된 칸을 차지한다. 한 단어를 두 줄에 나누어 쓸 수 없고, 단어 중간에 빈칸이 들어갈 수 없다.
4. 글은 좌우 양 끝에 맞추어 정렬해야 한다. 즉, 각 줄의 첫 단어는 첫 번째 칸에서 시작하고, 마지막 줄을 제외한 모든 줄의 마지막 단어는 $W$번째 칸에서 끝나야 한다.

어떤 배치에서 나타나는 연속된 빈칸의 최대 길이가 작을수록 보기 좋은 글이라고 하자. 연속된 빈칸의 최대 길이가 가능한 한 작아지도록 배치한 것을 아름다운 레이아웃이라고 부른다. 단, 마지막 줄에서 마지막 단어 뒤에 남는 빈칸은 세지 않는다.

예를 들어 길이가 각각 $4, 2, 1, 3$인 네 단어(예: "This is a pen")를 $11$칸짜리 원고지에 규칙에 맞게 쓰면, 연속된 빈칸의 최대 길이를 최소 $2$까지 줄일 수 있다. 반면 같은 네 단어를 규칙에 맞게 배치하더라도 연속된 빈칸의 최대 길이가 $3$인, 아름답지 않은 레이아웃도 존재한다.

각 단어의 길이와 원고지의 칸 수 $W$가 주어질 때, 규칙을 지키면서 만들 수 있는 아름다운 레이아웃에서 연속된 빈칸의 최대 길이를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫째 줄에는 두 정수 $W$와 $N$이 주어진다. $W$는 원고지의 칸 수이고, $N$은 단어의 개수이다. ($3 \le W \le 80000$, $2 \le N \le 50000$)

둘째 줄에는 $N$개의 정수 $x_1, x_2, \dots, x_N$이 주어지며, $x_i$는 $i$번째 단어의 길이이다. ($1 \le x_i \le (W-1)/2$)

규칙을 만족하는 배치가 항상 존재함이 보장된다.

입력의 마지막 줄에는 $0$이 두 개 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 아름다운 레이아웃에서 나타나는 연속된 빈칸의 최대 길이를 한 줄에 하나씩 출력한다.