Problems
Compression
Compression
Vasya is not satisfied with the quality of the spam filter in his mailbox and decided to build his own. He has prepared a list \textbf{L_0} of \textbf{1} ≤ \textbf{N_0} ≤ \textbf{5·10^4} words. Each of the words is at least \textbf{1} and at most \textbf{40} characters long. In his opinion, any message that contains even one of those words is spam.
\includegraphics{https://static.e-olymp.com/content/c1/c1e5657c445a0882d39a01c1538cf1a9c936ba83.jpg}
\includegraphics{file:///E:/2012-2013/ACM/BSU-2012/problems/compression/statements/.html/russian/55769d612ffdece1c0167001ae185df8d8aac11c.png}
The list is quite big and Vasya wants to compress it. More precisely: he wants to replace the list \textbf{L_0} with a list \textbf{L_1}, of non-empty words such that for every word \textbf{w_0L_0} exists a word \textbf{w_1L_1}, where \textbf{w}_1 is a prefix of \textbf{w_0}. Obviously, if the words in \textbf{L_1} are too short, then too many messages will be falsely qualified as spam. After some thinking, Vasya came up with the following condition: he wants to find the list \textbf{L_1} so as to minimize the penalty where \textbf{|w|} denotes the length of the word \textbf{w}.
Help him solve this problem.
\InputFile
The first input line contains \textbf{N_0}, the number of words in the list \textbf{L_0}. The following \textbf{N_0} lines contain the words from the list \textbf{L_0}, consisting of lowercase letters only.
\OutputFile
The first output line should contain the value of \textbf{P} corresponding to the optimal list \textbf{L_1}. The second line should contain \textbf{N_1}, the number of words in the list \textbf{L_1}. The following lines should contain the words from the list \textbf{L_1}. If there are several optimal solutions, any one of them is acceptable.
Input example #1
4 abxcaba abax abay abaz
Output example #1
146028888064 2 aba abxcaba