{"raw_statement":[{"iden":"statement","content":"Vasya and Petya take part in a Codeforces round. The round lasts for two hours and contains five problems.\n\nFor this round the dynamic problem scoring is used. If you were lucky not to participate in any Codeforces round with dynamic problem scoring, here is what it means. The maximum point value of the problem depends on the ratio of the number of participants who solved the problem to the total number of round participants. Everyone who made at least one submission is considered to be participating in the round.\n\nPay attention to the range bounds. For example, if 40 people are taking part in the round, and 10 of them solve a particular problem, then the solvers fraction is equal to 1 / 4, and the problem's maximum point value is equal to 1500.\n\nIf the problem's maximum point value is equal to _x_, then for each whole minute passed from the beginning of the contest to the moment of the participant's correct submission, the participant loses _x_ / 250 points. For example, if the problem's maximum point value is 2000, and the participant submits a correct solution to it 40 minutes into the round, this participant will be awarded with 2000·(1 - 40 / 250) = 1680 points for this problem.\n\nThere are _n_ participants in the round, including Vasya and Petya. For each participant and each problem, the number of minutes which passed between the beginning of the contest and the submission of this participant to this problem is known. It's also possible that this participant made no submissions to this problem.\n\nWith two seconds until the end of the round, all participants' submissions have passed pretests, and not a single hack attempt has been made. Vasya believes that no more submissions or hack attempts will be made in the remaining two seconds, and every submission will pass the system testing.\n\nUnfortunately, Vasya is a cheater. He has registered 109 + 7 new accounts for the round. Now Vasya can submit any of his solutions from these new accounts in order to change the maximum point values of the problems. Vasya can also submit any wrong solutions to any problems. Note that Vasya can not submit correct solutions to the problems he hasn't solved.\n\nVasya seeks to score strictly more points than Petya in the current round. Vasya has already prepared the scripts which allow to obfuscate his solutions and submit them into the system from any of the new accounts in just fractions of seconds. However, Vasya doesn't want to make his cheating too obvious, so he wants to achieve his goal while making submissions from the smallest possible number of new accounts.\n\nFind the smallest number of new accounts Vasya needs in order to beat Petya (provided that Vasya's assumptions are correct), or report that Vasya can't achieve his goal."},{"iden":"input","content":"The first line contains a single integer _n_ (2 ≤ _n_ ≤ 120) — the number of round participants, including Vasya and Petya.\n\nEach of the next _n_ lines contains five integers _a__i_, 1, _a__i_, 2..., _a__i_, 5 ( - 1 ≤ _a__i_, _j_ ≤ 119) — the number of minutes passed between the beginning of the round and the submission of problem _j_ by participant _i_, or _\\-1_ if participant _i_ hasn't solved problem _j_.\n\nIt is guaranteed that each participant has made at least one successful submission.\n\nVasya is listed as participant number 1, Petya is listed as participant number 2, all the other participants are listed in no particular order."},{"iden":"output","content":"Output a single integer — the number of new accounts Vasya needs to beat Petya, or _\\-1_ if Vasya can't achieve his goal."},{"iden":"examples","content":"Input\n\n2\n5 15 40 70 115\n50 45 40 30 15\n\nOutput\n\n2\n\nInput\n\n3\n55 80 10 -1 -1\n15 -1 79 60 -1\n42 -1 13 -1 -1\n\nOutput\n\n3\n\nInput\n\n5\n119 119 119 119 119\n0 0 0 0 -1\n20 65 12 73 77\n78 112 22 23 11\n1 78 60 111 62\n\nOutput\n\n27\n\nInput\n\n4\n-1 20 40 77 119\n30 10 73 50 107\n21 29 -1 64 98\n117 65 -1 -1 -1\n\nOutput\n\n\\-1"},{"iden":"note","content":"In the first example, Vasya's optimal strategy is to submit the solutions to the last three problems from two new accounts. In this case the first two problems will have the maximum point value of 1000, while the last three problems will have the maximum point value of 500. Vasya's score will be equal to 980 + 940 + 420 + 360 + 270 = 2970 points, while Petya will score just 800 + 820 + 420 + 440 + 470 = 2950 points.\n\nIn the second example, Vasya has to make a single unsuccessful submission to any problem from two new accounts, and a single successful submission to the first problem from the third new account. In this case, the maximum point values of the problems will be equal to 500, 1500, 1000, 1500, 3000. Vasya will score 2370 points, while Petya will score just 2294 points.\n\nIn the third example, Vasya can achieve his goal by submitting the solutions to the first four problems from 27 new accounts. The maximum point values of the problems will be equal to 500, 500, 500, 500, 2000. Thanks to the high cost of the fifth problem, Vasya will manage to beat Petya who solved the first four problems very quickly, but couldn't solve the fifth one."}],"translated_statement":[{"iden":"statement","content":"Vasya 和 Petya 参加了一场 Codeforces 比赛。比赛时长为两小时，包含五道题。\n\n本场比赛使用动态题目分值机制。如果你从未参加过使用动态题目分值的 Codeforces 比赛，以下是其含义：一道题的最大分值取决于解出该题的参赛者数量与总参赛者数量的比率。所有至少提交过一次的选手均被视为参赛者。\n\n\n\n请注意范围边界。例如，如果共有 40 名选手参赛，其中 10 人解出某道题，则解题比例为 #cf_span[1 / 4]，该题的最大分值为 1500。\n\n若一道题的最大分值为 #cf_span[x]，则从比赛开始到选手提交正确解答的每整分钟，选手将损失 #cf_span[x / 250] 分。例如，若一道题的最大分值为 2000，选手在比赛开始后 40 分钟提交正确解答，则该选手将获得 #cf_span[2000·(1 - 40 / 250) = 1680] 分。\n\n本场比赛共有 #cf_span[n] 名选手，包括 Vasya 和 Petya。对于每位选手和每道题，已知该选手提交该题所经过的分钟数。也可能该选手未提交该题。\n\n在比赛还剩两秒时，所有选手的提交均已通过预测试，且尚未有任何 hack 尝试。Vasya 认为在剩余的两秒内不会再有新的提交或 hack 行为，且所有提交都将通过系统测试。\n\n不幸的是，Vasya 是个作弊者。他为本次比赛注册了 #cf_span[109 + 7] 个新账号。现在 Vasya 可以从这些新账号提交他已解决的任何题目，以改变题目的最大分值。Vasya 也可以向任何题目提交错误解答。注意，Vasya 不能向他未解决的题目提交正确解答。\n\nVasya 希望在本次比赛中获得比 Petya 严格更多的分数。Vasya 已经编写了脚本，可以在几分之一秒内将他的解决方案从任意新账号混淆并提交到系统。但 Vasya 不想让作弊过于明显，因此他希望以最少的新账号数量达成目标。\n\n求出 Vasya 为击败 Petya 所需的最少新账号数量（假设 Vasya 的假设正确），或判断 Vasya 无法达成目标。\n\n第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 120]) —— 包括 Vasya 和 Petya 在内的比赛参赛者数量。\n\n接下来的 #cf_span[n] 行每行包含五个整数 #cf_span[ai, 1, ai, 2..., ai, 5] (#cf_span[ - 1 ≤ ai, j ≤ 119]) —— 第 #cf_span[i] 位选手提交第 #cf_span[j] 题所经过的分钟数，若该选手未解出该题则为 _-1_。\n\n保证每位选手至少有一次成功提交。\n\nVasya 为第 1 号选手，Petya 为第 2 号选手，其余选手顺序任意。\n\n输出一个整数 —— Vasya 为击败 Petya 所需的新账号数量，若无法达成目标则输出 _-1_。","id":"statement"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n] (#cf_span[2 ≤ n ≤ 120]) —— 包括 Vasya 和 Petya 在内的比赛参赛者数量。接下来的 #cf_span[n] 行每行包含五个整数 #cf_span[ai, 1, ai, 2..., ai, 5] (#cf_span[ - 1 ≤ ai, j ≤ 119]) —— 第 #cf_span[i] 位选手提交第 #cf_span[j] 题所经过的分钟数，若该选手未解出该题则为 _-1_。保证每位选手至少有一次成功提交。Vasya 为第 1 号选手，Petya 为第 2 号选手，其余选手顺序任意。","id":"input"},{"iden":"output","content":"输出一个整数 —— Vasya 为击败 Petya 所需的新账号数量，若无法达成目标则输出 _-1_。","id":"output"},{"iden":"examples","content":"输入\n2\n5 15 40 70 115\n50 45 40 30 15\n输出\n2\n\n输入\n3\n55 80 10 -1 -1\n15 -1 79 60 -1\n42 -1 13 -1 -1\n输出\n3\n\n输入\n5\n119 119 119 119 119\n0 0 0 0 -1\n20 65 12 73 77\n78 112 22 23 11\n1 78 60 111 62\n输出\n27\n\n输入\n4\n-1 20 40 77 119\n30 10 73 50 107\n21 29 -1 64 98\n117 65 -1 -1 -1\n输出\n-1","id":"examples"},{"iden":"note","content":"在第一个例子中，Vasya 的最优策略是从两个新账号提交最后三道题的解答。此时前两道题的最大分值为 1000，后三道题的最大分值为 500。Vasya 的得分将为 #cf_span[980 + 940 + 420 + 360 + 270 = 2970] 分，而 Petya 的得分仅为 #cf_span[800 + 820 + 420 + 440 + 470 = 2950] 分。\n\n在第二个例子中，Vasya 必须从两个新账号向任意一道题提交一次错误提交，并从第三个新账号向第一道题提交一次正确提交。此时各题最大分值为 500、1500、1000、1500、3000。Vasya 得分为 2370 分，而 Petya 得分为 2294 分。\n\n在第三个例子中，Vasya 可以通过从 27 个新账号提交前四道题的解答来达成目标。此时各题最大分值为 500、500、500、500、2000。由于第五题分值很高，Vasya 能够击败 Petya，后者虽然快速解出了前四题，但未能解出第五题。","id":"note"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ 2 \\leq n \\leq 120 $, be the number of participants.  \nLet $ A = (a_{i,j}) \\in (\\mathbb{Z} \\cup \\{-1\\})^{n \\times 5} $ be the submission matrix, where $ a_{i,j} $ is the submission time (in minutes) of participant $ i $ for problem $ j $, or $ -1 $ if unsolved.  \nLet $ V = a_{1,\\cdot} $ be Vasya’s submission vector.  \nLet $ P = a_{2,\\cdot} $ be Petya’s submission vector.  \n\nLet $ s_j \\in \\mathbb{Z}_{\\geq 0} $ be the number of participants who solved problem $ j $, including Vasya’s original account and any new accounts he adds.  \nLet $ x \\in \\mathbb{Z}_{\\geq 0} $ be the number of new accounts Vasya creates.  \nLet $ d_j \\in \\mathbb{Z}_{\\geq 0} $ be the number of new accounts Vasya uses to submit a correct solution to problem $ j $, with $ \\sum_{j=1}^5 d_j = x $.  \nLet $ w_j \\in \\mathbb{Z}_{\\geq 0} $ be the number of new accounts Vasya uses to submit *wrong* solutions to problem $ j $ (or any problem).  \n\nTotal participants: $ n + x $.  \nSolvers of problem $ j $: $ s_j = \\mathbb{I}(a_{1,j} \\neq -1) + \\mathbb{I}(a_{2,j} \\neq -1) + \\sum_{i=3}^n \\mathbb{I}(a_{i,j} \\neq -1) + d_j $.  \n\nThe maximum point value of problem $ j $ is:  \n$$  \nm_j = \n\\begin{cases} \n3000 & \\text{if } \\frac{s_j}{n+x} \\geq \\frac{3}{4} \\\\ \n2000 & \\text{if } \\frac{1}{2} \\leq \\frac{s_j}{n+x} < \\frac{3}{4} \\\\ \n1500 & \\text{if } \\frac{1}{4} \\leq \\frac{s_j}{n+x} < \\frac{1}{2} \\\\ \n1000 & \\text{if } \\frac{1}{10} \\leq \\frac{s_j}{n+x} < \\frac{1}{4} \\\\ \n500 & \\text{if } \\frac{s_j}{n+x} < \\frac{1}{10} \n\\end{cases}\n$$  \n\nVasya’s score for problem $ j $:  \n$$  \nv_j = \n\\begin{cases} \nm_j \\cdot \\left(1 - \\frac{a_{1,j}}{250}\\right) & \\text{if } a_{1,j} \\neq -1 \\\\ \n0 & \\text{if } a_{1,j} = -1 \n\\end{cases}\n$$  \n\nPetya’s score for problem $ j $:  \n$$  \np_j = \n\\begin{cases} \nm_j \\cdot \\left(1 - \\frac{a_{2,j}}{250}\\right) & \\text{if } a_{2,j} \\neq -1 \\\\ \n0 & \\text{if } a_{2,j} = -1 \n\\end{cases}\n$$  \n\nTotal scores:  \n$ S_V = \\sum_{j=1}^5 v_j $,  \n$ S_P = \\sum_{j=1}^5 p_j $.  \n\n**Constraints**  \n1. $ d_j \\geq 0 $, $ w_j \\geq 0 $, $ x = \\sum_{j=1}^5 d_j + \\sum_{j=1}^5 w_j $  \n2. $ s_j = \\text{base\\_solvers}_j + d_j $, where $ \\text{base\\_solvers}_j = \\sum_{i=1}^n \\mathbb{I}(a_{i,j} \\neq -1) $  \n3. $ n + x \\geq 1 $  \n4. $ w_j $ can be distributed arbitrarily; only $ d_j $ affects $ s_j $.  \n5. Vasya cannot submit correct solutions to problems he did not originally solve: $ d_j = 0 $ if $ a_{1,j} = -1 $.  \n\n**Objective**  \nFind the minimal $ x \\in \\mathbb{Z}_{\\geq 0} $ such that $ S_V > S_P $,  \nor return $ -1 $ if no such $ x $ exists.","simple_statement":null,"has_page_source":false}