아름다운 레이아웃

시간 제한5초메모리 제한128 MB

요약

단어 길이들과 폭 W가 주어질 때 줄바꿈을 정해 양쪽 정렬했을 때 생기는 연속 공백의 최댓값이 가장 작아지도록 배치하고 그 값을 구합니다.

난이도: 보통10점 중 7점
유형: 이분 탐색, 그리디, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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

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

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

출력

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

예제1

예제 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

예상 출력