English · Original
Chinese · Translation
Formal · Original
Vasya and Petya take part in a Codeforces round. The round lasts for two hours and contains five problems.
For 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.
Pay 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.
If 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.
There 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.
With 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.
Unfortunately, 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.
Vasya 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.
Find 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.
## Input
The first line contains a single integer _n_ (2 ≤ _n_ ≤ 120) — the number of round participants, including Vasya and Petya.
Each 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_.
It is guaranteed that each participant has made at least one successful submission.
Vasya is listed as participant number 1, Petya is listed as participant number 2, all the other participants are listed in no particular order.
## Output
Output a single integer — the number of new accounts Vasya needs to beat Petya, or _\-1_ if Vasya can't achieve his goal.
[samples]
## Note
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.
In 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.
In 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.
Vasya 和 Petya 参加了一场 Codeforces 比赛。比赛时长为两小时，包含五道题目。
本场比赛使用动态题目分值机制。如果你从未参加过使用动态题目分值的 Codeforces 比赛，以下是其含义：题目最大分值取决于解出该题的参赛者数量与比赛总参赛者数量的比值。所有至少提交过一次的参赛者均被视为参加比赛。
请注意范围边界。例如，如果比赛有 40 名参赛者，其中 10 人解出某道题，则解题比例为 $1/4$，该题的最大分值为 1500。
若某题的最大分值为 $x$，则从比赛开始到参赛者提交正确解答的每完整一分钟，该参赛者将扣除 $x/250$ 分。例如，若某题最大分值为 2000，参赛者在比赛开始后 40 分钟提交正确解答，则该参赛者将获得 $2000·(1 - 40/250) = 1680$ 分。
比赛共有 $n$ 名参赛者，包括 Vasya 和 Petya。对于每位参赛者和每道题，已知从比赛开始到该参赛者提交该题所经过的分钟数。也可能该参赛者未提交该题。
在比赛还剩两秒时，所有参赛者的提交均已通过预测试，且尚未有任何 hack 尝试。Vasya 认为在剩余的两秒内不会再有新的提交或 hack 行为，且所有提交都将通过系统测试。
不幸的是，Vasya 是一个作弊者。他为本次比赛注册了 $10^9 + 7$ 个新账户。现在 Vasya 可以从这些新账户提交他已解出的任何题目，以改变题目的最大分值。Vasya 也可以向任何题目提交错误解答。注意，Vasya 不能向他未解出的题目提交正确解答。
Vasya 希望在本次比赛中获得严格多于 Petya 的分数。Vasya 已经准备好脚本，可以在几分之一秒内从任意新账户提交混淆后的解决方案。但 Vasya 不希望作弊行为过于明显，因此他希望在使用最少数量的新账户的情况下实现目标。
请找出 Vasya 为击败 Petya 所需的最少新账户数量（假设 Vasya 的假设成立），或报告 Vasya 无法达成目标。
第一行包含一个整数 $n$ ($2 ≤ n ≤ 120$) —— 包括 Vasya 和 Petya 在内的比赛参赛者数量。
接下来的 $n$ 行，每行包含五个整数 $a_{i,1}, a_{i,2}, ..., a_{i,5}$ ($-1 ≤ a_{i,j} ≤ 119$) —— 第 $i$ 位参赛者提交第 $j$ 题所经过的分钟数，若第 $i$ 位参赛者未解出第 $j$ 题则为 _-1_。
保证每位参赛者至少有一次成功提交。
Vasya 被列为第 1 号参赛者，Petya 被列为第 2 号参赛者，其余参赛者顺序任意。
输出一个整数 —— Vasya 为击败 Petya 所需的新账户数量，若无法达成目标则输出 _-1_。
## Input
第一行包含一个整数 $n$ ($2 ≤ n ≤ 120$) —— 包括 Vasya 和 Petya 在内的比赛参赛者数量。接下来的 $n$ 行，每行包含五个整数 $a_{i,1}, a_{i,2}, ..., a_{i,5}$ ($-1 ≤ a_{i,j} ≤ 119$) —— 第 $i$ 位参赛者提交第 $j$ 题所经过的分钟数，若第 $i$ 位参赛者未解出第 $j$ 题则为 _-1_。保证每位参赛者至少有一次成功提交。Vasya 被列为第 1 号参赛者，Petya 被列为第 2 号参赛者，其余参赛者顺序任意。
## Output
输出一个整数 —— Vasya 为击败 Petya 所需的新账户数量，若无法达成目标则输出 _-1_。
[samples]
## Note
在第一个例子中，Vasya 的最优策略是从两个新账户提交最后三道题的解答。此时前两题的最大分值为 1000，后三题的最大分值为 500。Vasya 的得分将为 $980 + 940 + 420 + 360 + 270 = 2970$ 分，而 Petya 的得分仅为 $800 + 820 + 420 + 440 + 470 = 2950$ 分。
在第二个例子中，Vasya 必须从两个新账户向任意一题提交一次错误解答，并从第三个新账户向第一题提交一次正确解答。此时各题最大分值分别为 500、1500、1000、1500、3000。Vasya 将获得 2370 分，而 Petya 仅获得 2294 分。
在第三个例子中，Vasya 可以通过从 27 个新账户提交前四题的解答来达成目标。此时各题最大分值分别为 500、500、500、500、2000。由于第五题分值很高，Vasya 能够击败 Petya，后者虽然快速解出了前四题，但未能解出第五题。
**Definitions**
Let $ n \in \mathbb{Z} $, $ 2 \leq n \leq 120 $, be the number of participants.
Let $ A = (a_{i,j}) \in (\mathbb{Z} \cup \{-1\})^{n \times 5} $, where $ a_{i,j} $ is the submission time (in minutes) of participant $ i $ for problem $ j $, or $ -1 $ if unsolved.
Let $ V = a_{1,\cdot} $ be Vasya’s submission vector, $ P = a_{2,\cdot} $ be Petya’s.
Let $ s_j \in \{0, 1, \dots, n\} $ be the number of participants (including fake accounts) who solved problem $ j $.
Let $ f: \{0,1,\dots,n\} \to \{500, 1000, 1500, 2000, 2500, 3000\} $ be the dynamic scoring function:
$$
f(s) =
\begin{cases}
3000 & \text{if } s \leq \left\lfloor \frac{n}{10} \right\rfloor \\
2500 & \text{if } \left\lfloor \frac{n}{10} \right\rfloor < s \leq \left\lfloor \frac{n}{5} \right\rfloor \\
2000 & \text{if } \left\lfloor \frac{n}{5} \right\rfloor < s \leq \left\lfloor \frac{n}{2.5} \right\rfloor \\
1500 & \text{if } \left\lfloor \frac{n}{2.5} \right\rfloor < s \leq \left\lfloor \frac{n}{1.5} \right\rfloor \\
1000 & \text{if } \left\lfloor \frac{n}{1.5} \right\rfloor < s \leq \left\lfloor \frac{2n}{3} \right\rfloor \\
500 & \text{if } \left\lfloor \frac{2n}{3} \right\rfloor < s \leq n
\end{cases}
$$
Let $ x_j \in \mathbb{Z}_{\geq 0} $ be the number of fake accounts that solve problem $ j $.
Let $ y_j \in \mathbb{Z}_{\geq 0} $ be the number of fake accounts that submit *incorrectly* to problem $ j $.
Let $ t_j = s_j + x_j $ be the total solvers of problem $ j $, where $ s_j $ is the original number of solvers (excluding fakes).
**Constraints**
1. $ x_j = 0 $ if $ a_{1,j} = -1 $ (Vasya cannot solve a problem he didn’t solve).
2. $ x_j \geq 0 $, $ y_j \geq 0 $ for all $ j \in \{1, \dots, 5\} $.
3. Total fake accounts: $ F = \sum_{j=1}^5 (x_j + y_j) $.
4. The total number of participants becomes $ n + F $.
5. $ t_j = s_j + x_j \leq n + F $, and $ f(t_j) $ is computed using the new total $ n + F $.
**Objective**
Minimize $ F = \sum_{j=1}^5 (x_j + y_j) $ such that Vasya’s total score $ S_V > S_P $, where:
$$
S_V = \sum_{j=1}^5 \left[ f(t_j) \cdot \left(1 - \frac{a_{1,j}}{250}\right) \cdot \mathbf{1}_{a_{1,j} \geq 0} \right]
$$
$$
S_P = \sum_{j=1}^5 \left[ f(t_j) \cdot \left(1 - \frac{a_{2,j}}{250}\right) \cdot \mathbf{1}_{a_{2,j} \geq 0} \right]
$$
If no such $ (x_1, \dots, x_5, y_1, \dots, y_5) $ exists, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "B. Dynamic Problem Scoring",
"description": {
"content": "Vasya and Petya take part in a Codeforces round. The round lasts for two hours and contains five problems. For this round the dynamic problem scoring is used. If you were lucky not to participate in ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF773B"
},
"statements": [
{
"statement_type": "Markdown",
"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 ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Vasya 和 Petya 参加了一场 Codeforces 比赛。比赛时长为两小时，包含五道题目。\n\n本场比赛使用动态题目分值机制。如果你从未参加过使用动态题目分值的 Codeforces 比赛，以下是其含义：题目最大分值取决于解出该题的参赛者数量与比赛总参赛者数量的比值。所有至少提交过一次的参赛者均被视为参加比赛。\n\n请注意范围边界。例如，如果比赛有 40 名参赛者，其中 10 人解出某道题，...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**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} $, where $ a_{i,j} $ is the submission...",
"is_translate": false,
"language": "Formal"
}
]
}