Олимпиадный тренинг

Задача 23588. voids in the cube


Задача

Темы:
The jury has compiled a report on the computer science training camp and is going to print it on a standard sheet of paper. The entire report is typed in one monospace font, i.e. all characters (including spaces) are the same width. The line length when printed with this font on a sheet of paper is S.
 
Let's call a void a sequence of spaces between adjacent words in a line, as well as from the beginning of the line to the first word in it and from the last word in the line to the end of the line. The problem facing the jury is that Vladimir Mikhailovich Kiryukhin, scientific director of the collection, refuses to read the text if the sum of the cubes of void lengths for all lines is not minimal. Help the jury arrange the report on a piece of paper so that V.M. Kiryukhin agreed to read it and approve the results of the training camp.
 
To achieve the required arrangement of text on paper, it is allowed to replace an arbitrary whitespace sequence (that is, a non-empty sequence of consecutive spaces or line breaks) with any other whitespace sequence.
 
Input
The first line of the input file contains the integer S (1<=S<=80). 
The following lines contain a report containing no more than 500 words. 
The length of each line of the report does not exceed 250 characters, and the length of each word does not exceed S.
 
Output
Output in the first line of the output file the minimum possible amount 
void cubes across all rows. In subsequent lines, output 
the desired location of the text on a sheet of paper.
 
Sample input file
30
Winners of the Summer Informatics Training Camp 1997:
Vladimir Martyanov,
Anatoly Ponomarev,
Nikolai Durov,
Andrey Lopatin.
 
Sample output file
325
     Winners     summer    
training camps by
 informatics 1997: Vladimir
Martyanov, Anatoly Ponomarev,
Nikolay Durov, Andrey Lopatin.