F. Рудольф и рифмы
ограничение по времени на тест
1 с
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Будучи экспертом по риторике и NLP, Рудольф много времени проводит на различных форумах и в различных онлайн-обсуждениях. Однако, недавно он узнал про новейшие достижения науки в области искусственного интеллекта и решил разработать алгоритм, который отвечал бы за него на вопросы в интернете, при этом оставляя качество ответов наилучшим возможным.

Рудольф заранее знает, что ему нужно будет ответить ровно на $$$n$$$ вопросов, и поэтому подготавливает $$$n$$$ различных строк — ответы на предстоящие вопросы. Затем, алгоритм получает на вход $$$n$$$ вопросов и должен будет сопоставить вопросы и ответы некоторым образом. Конечно, чтобы остроумность Рудольфа не оказалась под сомнением, каждый из ответов должен быть использован ровно один раз.

Общеизвестный факт, что Рудольф мастер слова и рифмы, а потому искусственный интеллект должен быть достаточно умным, чтобы провести собеседников и выдавать максимально оригинальные и подходящие под ситуацию ответы. Для оценки качества алгоритма Рудольф придумал следующую метрику:

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

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

Входные данные

В первой строке задано число $$$n$$$ — число вопросов и ответов ($$$1 \le n \le 800$$$). Затем $$$n$$$ строк с вопросами. Затем $$$n$$$ строк с возможными ответами.

Каждая строка состоит из строчных латинских букв, пробелов и символов "?", "!" и ")".

Суммарная длина строк не превосходит $$$200000$$$.

Выходные данные

В первой строке выведите ответ — полученное значение метрики (сумму рифмованности по всем парам вопрос-ответ). Затем в $$$2n$$$ строках выведите пары вопрос-ответ: вопросы в том же порядке, что и во входных данных, после каждого вопроса ответ на него.

Примеры
Входные данные
5
zdraste!
kak dela?
gde byl?
a voobshe kak sam?
horosho poka
poka ne rodila
pivo pyl
zabor pokraste
ne zabud vyrvat dvoiku s dnevnika
privet tvoei madam
Выходные данные
13
zdraste!
zabor pokraste
kak dela?
poka ne rodila
gde byl?
pivo pyl
a voobshe kak sam?
privet tvoei madam
horosho poka
ne zabud vyrvat dvoiku s dnevnika
Входные данные
5
here comes adamant!
i hope he will add anime to contest!
is it rated?
well, have fun and good luck!
when the ratings would update??
you sure will fail iq test
when you would have a date))
try not to suck)
he does not use deodarant
obosrated!
Выходные данные
19
here comes adamant!
he does not use deodarant
i hope he will add anime to contest!
you sure will fail iq test
is it rated?
obosrated!
well, have fun and good luck!
try not to suck)
when the ratings would update??
when you would have a date))
Примечание

Предположим, мы хотим подсчитать рифмованность для строк

"abc d ef!!!" и "lol k e k cd?)ef?"

Для подсчета рифмованности убираем все символы из строк, кроме маленьких букв: "abcdef", "lolkekcdef" и вычисляем длину общего суффикса. Она равна 4.