텍스트 정렬하기

이메일을 쓰는 일은 즐겁지만, 안타깝게도 각 줄의 길이가 제각각이라 보기 좋게 정리되지 않는 경우가 많습니다. 대표단은 깔끔하게 정렬된 이메일을 보내고 싶어 하며, 여러분이 할 일은 이들을 위한 이메일 정렬 프로그램을 작성하는 것입니다.

가장 간단한 방법은 너무 짧은 줄의 단어 사이에 공백을 더 끼워 넣는 것입니다. 하지만 이것이 최선은 아닙니다. 다음 예를 살펴봅시다.

****************************
This is the example you are
actually considering.

각 줄을 별표(*) 한 줄과 같은 길이로 맞추고 싶다고 합시다. 단순히 공백만 끼워 넣으면 다음과 같이 됩니다.

****************************
This is the example you  are
actually        considering.

하지만 둘째 줄의 큰 공백 때문에 오히려 어색해 보입니다. 단어 "are"를 첫째 줄에서 둘째 줄로 옮기면 더 나은 결과를 얻습니다.

****************************
This  is  the  example   you
are  actually   considering.

이를 형식화해 봅시다. 두 단어 사이의 각 틈(gap)마다 나쁨(badness) 점수를 매깁니다. 공백이 $n$칸인 틈의 나쁨은 $(n-1)^2$입니다. 프로그램의 목표는 모든 틈의 나쁨의 합을 최소화하는 것입니다. 예를 들어 첫 번째 배치의 나쁨은 $1 + 7^2 = 50$이고, 두 번째 배치의 나쁨은 $1 + 1 + 1 + 4 + 1 + 4 = 12$로 훨씬 작습니다.

출력에서 모든 줄은 단어로 시작하고 단어로 끝나야 합니다. 즉, 줄의 맨 앞이나 맨 뒤에는 공백이 올 수 없습니다. 유일한 예외는 단어가 하나뿐인 줄입니다. 이런 줄은 그 단어를 줄의 맨 앞에 두는 조건으로 출력할 수 있습니다. 이런 줄이 목표 너비보다 짧으면 나쁨 500이 부여됩니다. 물론 이때 줄의 길이는 그 한 단어의 길이입니다.

입력은 여러 개의 문단으로 이루어진 텍스트입니다. 각 문단 앞에는 그 문단의 목표 너비를 나타내는 정수 $N$이 한 줄에 하나씩 주어지며, $1 \le N \le 80$입니다. 문단은 0개 이상의 줄로 이루어지고, 각 줄에는 하나 이상의 단어가 있습니다. 단어는 ASCII 코드 33부터 126까지의 문자로 이루어지며, 하나 이상의 공백으로 구분됩니다. 어떤 단어도 그 문단의 목표 너비보다 길지 않습니다. 한 문단에 속한 모든 단어의 길이 합은 10000자를 넘지 않습니다. 어떤 줄도 100자를 넘지 않습니다.

각 문단은 정확히 하나의 빈 줄로 끝납니다. 문단의 개수에는 제한이 없습니다. 입력은 $N = 0$으로 시작하는 문단 설명으로 끝나며, 이 문단은 처리하지 않습니다.

각 문단에 대해 가능한 가장 낮은 나쁨을 갖는 배치를 찾아, 그 최소 나쁨을 $B$라 할 때 Minimal badness is B. 형식의 문장을 출력하세요.