{"raw_statement":[{"iden":"statement","content":"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.\n\nRudolph 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.\n\nIt 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.\n\nThe 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.\n\nYou 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.\n\nThe first line contains a single integer $n$ – the number of questions and answers ($1 <= n <= 800$). Each of the following $n$ lines has one string — a question. Then, each of the following $n$ lines has one string — an answer.\n\nEach string consists of lowercase Latin letters, spaces and symbols \"?\" \"!\" and \")\".\n\nTotal length of all strings does not exceed $200000$.\n\nThe 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 $2 n$ 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.\n\nSuppose that we want to calculate rhyming for the pair\n\n\"abc d ef!!!\" and \"lol k e k cd?)ef?\"\n\nTo 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.\n\n"},{"iden":"input","content":"The first line contains a single integer $n$ – the number of questions and answers ($1 <= n <= 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$."},{"iden":"output","content":"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 $2 n$ 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."},{"iden":"examples","content":"Input5\nzdraste!\nkak dela?\ngde byl?\na voobshe kak sam?\nhorosho poka\npoka ne rodila\npivo pyl\nzabor pokraste\nne zabud vyrvat dvoiku s dnevnika\nprivet tvoei madam\nOutput13\nzdraste!\nzabor pokraste\nkak dela?\npoka ne rodila\ngde byl?\npivo pyl\na voobshe kak sam?\nprivet tvoei madam\nhorosho poka\nne zabud vyrvat dvoiku s dnevnika\nInput5\nhere comes adamant!\ni hope he will add anime to contest!\nis it rated?\nwell, have fun and good luck!\nwhen the ratings would update??\nyou sure will fail iq test\nwhen you would have a date))\ntry not to suck)\nhe does not use deodarant\nobosrated!\nOutput19\nhere comes adamant!\nhe does not use deodarant\ni hope he will add anime to contest!\nyou sure will fail iq test\nis it rated?\nobosrated!\nwell, have fun and good luck!\ntry not to suck)\nwhen the ratings would update??\nwhen you would have a date))\n"},{"iden":"note","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ n \\leq 800 $.  \nLet $ Q = (q_1, \\dots, q_n) $ be the sequence of question strings.  \nLet $ A = (a_1, \\dots, a_n) $ be the sequence of answer strings.  \n\nFor any string $ s $, define $ \\text{clean}(s) $ as the string obtained by removing all characters except lowercase Latin letters.  \nFor two strings $ x, y $, define $ \\text{rhyme}(x, y) = |\\text{lcsuf}(\\text{clean}(x), \\text{clean}(y))| $, where $ \\text{lcsuf}(u, v) $ is the longest common suffix of $ u $ and $ v $.  \n\n**Constraints**  \n1. Total length of all strings in $ Q \\cup A $ is $ \\leq 200000 $.  \n2. Each answer must be used exactly once; each question matched to exactly one answer.  \n\n**Objective**  \nFind a permutation $ \\sigma \\in S_n $ maximizing:  \n$$\n\\sum_{i=1}^{n} \\text{rhyme}(q_i, a_{\\sigma(i)})\n$$  \nOutput the maximum sum and a corresponding matching: for each $ i \\in \\{1, \\dots, n\\} $, output $ q_i $ followed by $ a_{\\sigma(i)} $.","simple_statement":"Given n questions and n answers, match each question to one answer (one-to-one) to maximize the total rhyming score.  \n\nRhyming score for a pair = length of the longest common suffix after keeping only lowercase letters.  \n\nOutput:  \n- Maximum total score  \n- Then n pairs: each question (in input order) followed by its matched answer","has_page_source":false}