들쭉날쭉, 들쭉날쭉

고정된 최대 너비 $L$(글자 수)에 맞추어 텍스트를 여러 줄로 배치하는 문제를 생각하자. 이를 흔히 줄 채우기(line filling) 라고 부른다.

배치를 잘 못하면 줄 끝이 불필요하게 들쭉날쭉해진다. 관례적으로 한 문단의 마지막 줄은 얼마든지 짧아도 되며 글자 몇 개만 있어도 상관없지만, 그 앞의 줄들은 열을 가득 채우도록 길이가 대체로 고르기를 기대한다.

각 줄에 들어갈 수 있는 만큼 단어를 채우고 다음 줄로 넘어가는 단순한 탐욕적 방법이 항상 가장 보기 좋은 결과를 주지는 않는다. 예를 들어 $L = 6$일 때 단어열 See if we care. 는

See if
we
care.

처럼 배치할 수도 있지만, 이는

See
if we
care.

보다 덜 보기 좋다.

단어란 줄의 시작이나 끝, 또는 공백으로 경계가 지어지는, 공백이 아닌 문자들의 연속을 뜻한다. 여기서 공백 문자는 빈칸과 줄바꿈 문자이다.

너비가 각각 $w_1, w_2, \ldots, w_N$ 인 $N$개의 단어와 최대 줄 너비 $L$이 주어진다(모든 $i$에 대해 $w_i \le L$). 단어 $i$부터 $j$까지를 담은 줄의 너비 $w(i, j)$를, 각 단어 너비의 합에 인접한 단어 사이마다 빈칸 하나씩을 더한 값으로 정의한다.

$$w(i, j) = \left(\sum_{k=i}^{j} w_k\right) + (j - i)$$

단어 $i$부터 $j$까지를 담은 줄의 들쭉날쭉함(raggedness) 은 다음과 같다.

$$r(i, j) = \bigl(L - w(i, j)\bigr)^2$$

어떤 줄도 $L$글자를 넘지 않도록 각 문단을 배치하되, 문단의 마지막 줄을 제외한 모든 줄의 들쭉날쭉함의 총합을 최소화하라. (문단의 마지막 줄은 위의 줄들보다 얼마든지 짧아도 된다.) 줄바꿈 문자는 줄 너비에 포함되지 않는다.

입력은 하나 이상의 데이터셋으로 이루어진다.

각 데이터셋은 최대 줄 너비 $L$(줄바꿈 문자 제외)을 나타내는 정수 하나가 담긴 줄로 시작하며, $0 < L \le 80$이다. 값이 $0$이면 입력의 끝을 뜻한다.

데이터셋의 나머지는 최대 $250$개의 줄에 걸친 한 문단의 텍스트이며, 빈 줄로 끝난다. 한 문단은 $1$개 이상 $500$개 이하의 단어를 포함하고, 단어는 공백이 아닌 문자들의 연속이다. 어떤 단어도 길이가 $L$글자를 넘지 않는다.

각 문단에 대해, 달성 가능한 최소 총 들쭉날쭉함을 한 줄에 출력하라. 이는 어떤 줄도 $L$글자를 넘지 않는 모든 올바른 배치 중에서, 마지막 줄을 제외한 모든 줄에 대한 $\sum r(i, j)$의 최솟값이다. 각 문단을 출력한 뒤에는 ===(등호 세 개)만 담긴 줄을 출력하라.

단어의 너비는 글자(문자) 수로 센다.