Как вы знаете, Уфа — город рэперов. Говорят, что для получения звания почетного жителя этого города нужно решить следующую задачу.

Вам предлагается написать куплет для вашей песни. Однако сами строки уже были выбраны за вас, и вам лишь остается расставить их в нужном порядке.

Предложенные строки настолько сложные, что любой слушатель захочет прочитать составленный вами текст для лучшего понимания. Именно поэтому ваша задача сделать упор на графическую рифму. Графическая рифма - это рифма из слов, окончания которых совпадают по написанию. Таким образом, качество куплета определяется суммой уровней созвучности всех пар соседних строк. Уровень созвучности двух строк определяется следующим образом:

• Пусть даны строки $$$a$$$ и $$$b$$$ длины $$$n$$$ и $$$m$$$ соответсвенно.
• Тогда уровень созвучности будет равен максимальному по длине совпадающему суффиксу двух данных строк. По-другому: он будет равен такому максимальному $$$i$$$ $$$(1 \le i \le min(n, m))$$$, что последние $$$i$$$ символов у данных строк будут совпадать. Формально говоря, $$$a_{n-i+1...n} = b_{m-i+1...m}$$$ (то есть для всех $$$j$$$ ($$$0 \le j \lt i$$$) верно, что $$$a_{n - j} = b_{m - j}$$$). Если $$$a_{n}$$$ не равен $$$b_{m}$$$, то уровень созвучности равен $$$0$$$.

Внимание! При подсчёте уровня созвучности учитываются абсолютно все символы, включая пробел и знаки препинания (ведь при чтении текста они выделяются интонацией, что тоже влияет на восприятие куплета).

Например, уровень созвучности строк "abac caba" и "babc caba" равен $$$6$$$, так как они имеют общий суффикс "c caba" длины $$$6$$$.

Вам дали набор $$$S$$$, состоящий из $$$n$$$ строк. Пусть $$$f(x, y)$$$ - уровень созвучности строк $$$x$$$ и $$$y$$$. Тогда качество куплета равно сумме $$$f(S_i, S_{i+1})$$$ $$$(1 \le i \le n-1)$$$. Требуется так расставить строки, чтобы качество куплета было максимальным. Гарантируется, что строки состоят из строчных букв английского алфавита a-z, знаков препинания ,.!?' и пробела.