{"problem":{"name":"F. Rudolph and Rhymes","description":{"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 d","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10263F"},"statements":[{"statement_type":"Markdown","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## Input\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.Each string consists of lowercase Latin letters, spaces and symbols \"?\" \"!\" and \")\".Total length of all strings does not exceed $200000$.\n\n## Output\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\n[samples]\n\n## Note\n\nSuppose 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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)} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10263F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}