{"problem":{"name":"I. Endeavor for perfection","description":{"content":"As a matter of fact, Dragon knows what Prince is interested in now. Prince uses to spend his rare off days learning different courses and trainings. But Dragon doubts whether he should tell Princess a","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10070I"},"statements":[{"statement_type":"Markdown","content":"As a matter of fact, Dragon knows what Prince is interested in now. Prince uses to spend his rare off days learning different courses and trainings. But Dragon doubts whether he should tell Princess about it.\n\nPrince decided that he needs some extra knowledge and skills. He chose n fields in which he wanted to gain knowledge and skills most of all. After this, he learned that m1, m2, ..., mn courses and trainings of each of fields exist.\n\nPrince took a close look at descriptions of courses and trainings and drew a table, in which sij is a value by which ith skill is increased after studying jth course (j = 1, 2, ..., mi).\n\nPrince believes that his basic knowledge and skills in all these fields are negligible, so they can be considered zero. He wants to evolve his knowledge and skills harmonically. In his opinion, he will reach the greatest harmony if he chooses one course for each field in such a way that difference between the highest and the lowest their increases would be as minimum as possible.\n\nYour task is to find the courses which Prince should choose.\n\nThe first line contains integer n (1 ≤ n ≤ 200) — the number of fields which Prince is interested in.\n\nThe second line contains n integers m1, m2, ..., mn (1 ≤ mj ≤ 1000,  j = 1, 2, ..., n) — the number of courses for each of fields. \n\nThe next n lines contain values sij (1 ≤ sij ≤ 109) — knowledges and skills, which Prince would gain at the courses. The first of these n lines contains values s11, s12, ..., s1m1, the second — values s21, s22, ..., s2m2, etc.\n\nThe values sij are listed in the numerical order of courses for each of the fields.\n\nIn the first line print one integer — minimum difference between the highest and the lowest numbers of increase.\n\nIn the second line print n integers — numbers of courses which Prince should choose. List the numbers in the same order in which the fields are listed. \n\nIf there is more than one answer — choose any of them.\n\n## Input\n\nThe first line contains integer n (1 ≤ n ≤ 200) — the number of fields which Prince is interested in.The second line contains n integers m1, m2, ..., mn (1 ≤ mj ≤ 1000,  j = 1, 2, ..., n) — the number of courses for each of fields. The next n lines contain values sij (1 ≤ sij ≤ 109) — knowledges and skills, which Prince would gain at the courses. The first of these n lines contains values s11, s12, ..., s1m1, the second — values s21, s22, ..., s2m2, etc.The values sij are listed in the numerical order of courses for each of the fields.\n\n## Output\n\nIn the first line print one integer — minimum difference between the highest and the lowest numbers of increase.In the second line print n integers — numbers of courses which Prince should choose. List the numbers in the same order in which the fields are listed. If there is more than one answer — choose any of them.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of fields.  \nFor each field $ i \\in \\{1, \\dots, n\\} $, let $ m_i \\in \\mathbb{Z}^+ $ be the number of courses available, and let $ S_i = (s_{i1}, s_{i2}, \\dots, s_{im_i}) $ be the sequence of skill increases for course $ j $ in field $ i $, where $ s_{ij} \\in \\mathbb{Z}^+ $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 200 $  \n2. $ 1 \\leq m_i \\leq 1000 $ for all $ i \\in \\{1, \\dots, n\\} $  \n3. $ 1 \\leq s_{ij} \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $, $ j \\in \\{1, \\dots, m_i\\} $\n\n**Objective**  \nChoose one course $ j_i \\in \\{1, \\dots, m_i\\} $ for each field $ i $, such that the difference $ \\max_{i} s_{i,j_i} - \\min_{i} s_{i,j_i} $ is minimized.  \nOutput the minimal difference and the sequence $ (j_1, j_2, \\dots, j_n) $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10070I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}