Formatting Text

Writing e-mails is fun, but unfortunately they often do not look very nice, mainly because the lines do not all have the same length. The summit representatives want to send nicely formatted e-mails, and your task is to write an e-mail formatting program for them.

The easiest way to do this would be to insert extra spaces between the words on lines that are too short. But that is not the best approach. Consider the following example:

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

Suppose we want every line to be as long as the row of stars. Simply inserting spaces would give:

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

This looks rather odd because of the large gap on the second line. Moving the word "are" from the first line to the second gives a better result:

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

To formalize this, we assign a badness to every gap between two words. A gap of $n$ spaces has badness $(n-1)^2$. The goal is to minimize the sum of all badnesses. For example, the badness of the first arrangement is $1 + 7^2 = 50$, whereas the badness of the second is only $1 + 1 + 1 + 4 + 1 + 4 = 12$.

In the output, every line must start and end with a word; that is, there can be no gap at the beginning or the end of a line. The only exception is a line that contains a single word: such a line may be output as long as the word is placed at the beginning of the line. If such a line is shorter than it should be, it is assigned a badness of 500. In this case the length of the line is simply the length of the single word.

The input consists of a text made up of several paragraphs. Each paragraph is preceded by a line containing a single integer $N$, the desired width of the paragraph, with $1 \le N \le 80$. A paragraph consists of zero or more lines, each containing one or more words. Words consist of characters with ASCII codes between 33 and 126 inclusive and are separated by spaces (possibly more than one). No word is longer than the desired width of its paragraph. The total length of all words in one paragraph is at most 10000 characters. No line is longer than 100 characters.

Each paragraph is terminated by exactly one blank line. There is no limit on the number of paragraphs. The input is terminated by a paragraph description starting with $N = 0$; this paragraph must not be processed.

For each paragraph, find the arrangement with the lowest possible badness and print the sentence Minimal badness is B., where $B$ is the badness of the best arrangement.