406970: GYM102638 F Rudolph and Rhymes

Being a true expert in rhetorics and NLP, Rudolph spends a lot of time on different forums and online discussions. Recently he has heard about some progress in artificial intelligence and decided to develop an algorithm to reply questions for him, keeping quality of the answers best possible.

Rudolph knows in advance that he will need to reply exactly $$$n$$$ questions, and that is why he prepares $$$n$$$ different strings — answers to the upcoming questions. Then, the algorithm takes $$$n$$$ questions as an input and matches them with the answers. Of course, in order for Rudolph's wit not to be doubted, each answer must be used exactly once.

It is a well known fact that Rudolph is a master of words and rhymes, and therefore artificial intelligence must be smart enough to give the most original and appropriate responses. To evaluate the quality of the algorithm, Rudolph came up with the following metric.

The value of the metric equals to the sum of rhyming values for each question-answer pair. The rhyming of one pair is evaluated as follows: all characters except lowercase Latin letters are removed from the question and answer, and the length of their largest common suffix is calculated. This length will be the rhyming value for this pair.

You need to develop such an algorithm to match the questions with answers and calculate the largest possible value of the metric. If there are several possible responses with optimal values of the metric, choose any.

The first line contains a single integer $$$n$$$ – the number of questions and answers ($$$1 \le n \le 800$$$). Each of the following $$$n$$$ lines has one string — a question. Then, each of the following $$$n$$$ lines has one string — an answer.

Each string consists of lowercase Latin letters, spaces and symbols "?" "!" and ")".

Total length of all strings does not exceed $$$200000$$$.

The first line of the output should contain the answer — optimal value of the metric (the sum of rhymings of all pairs question-answer). Then, in the following $$$2n$$$ lines print the pairs question-answer: questions in the same order, as in the input, and each question having the corresponding answer on the next line.

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))

Suppose that we want to calculate rhyming for the pair

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

To do this, we remove all the symbols, except for lowercase Latin letters: "abcdef", "lolkekcdef", and then we find the length of the longest common suffix, which is 4.