Dynamic Problem Scoring
Contest: VK Cup 2017 - Round 3
Difficulty rating: 2000
Tags: brute force, greedy

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.

$$\begin{array}{|c|c|}
\hline
\text{Solvers fraction} & \text{Maximum point value} \\
\hline
(1/2, 1] & 500 \\
(1/4, 1/2] & 1000 \\
(1/8, 1/4] & 1500 \\
(1/16, 1/8] & 2000 \\
(1/32, 1/16] & 2500 \\
[0, 1/32] & 3000 \\
\hline
\end{array}$$

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 format:
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 ai, 1, ai, 2..., ai, 5 ( - 1 ≤ ai, 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 format:
Output a single integer — the number of new accounts Vasya needs to beat Petya, or -1 if Vasya can't achieve his goal.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
2
5 15 40 70 115
50 45 40 30 15

Example output:
2

Example input:
3
55 80 10 -1 -1
15 -1 79 60 -1
42 -1 13 -1 -1

Example output:
3

Editorial:
Dynamic problem scoring used to be used more often in Codeforces rounds, including some tournament rounds like VK Cup 2015 Finals.
Once you read the problem statement carefully, the problem itself isn't overly difficult.
Consider new accounts Vasya puts into play. Correct solutions to which problems does he submit from these new accounts?
• If Vasya hasn't solved a problem, he can't submit correct solutions to it.
• If Vasya has solved a problem which Petya hasn't solved, then clearly Vasya wants the maximum point value of this problem to be as high as possible, thus it doesn't make sense to submit its solution from the new accounts.
• Suppose Vasya solved the problem at minute v, Petya solved it at minute p and the problem's maximum point value is m, then Vasya's and Petya's scores for this problem are m·(1 - v / 250) and m·(1 - p / 250), respectively. Let's denote the difference between these values by d = m·(p - v) / 250. Vasya wants to maximize this value.   If p - v is positive (that is, Vasya solved the problem faster than Petya), then d is maximized when m is maximized. To maximize m, Vasya shouldn't submit correct solutions to this problem from the new accounts.  On the other hand, if p - v is negative (that is, Petya solved the problem faster than Vasya), then d is maximized when m is minimized. To minimize m, Vasya should submit correct solutions to this problem from the new accounts.  Finally, if p - v is zero (that is, Petya and Vasya solved the problem at the same moment), then d = 0 for any value of m, so it doesn't matter if Vasya submits correct solutions to this problem or not.
• If p - v is positive (that is, Vasya solved the problem faster than Petya), then d is maximized when m is maximized. To maximize m, Vasya shouldn't submit correct solutions to this problem from the new accounts.
• On the other hand, if p - v is negative (that is, Petya solved the problem faster than Vasya), then d is maximized when m is minimized. To minimize m, Vasya should submit correct solutions to this problem from the new accounts.
• Finally, if p - v is zero (that is, Petya and Vasya solved the problem at the same moment), then d = 0 for any value of m, so it doesn't matter if Vasya submits correct solutions to this problem or not.
It follows from the above that Vasya should always do the same for all new accounts he puts into play.
Let's iterate over x — the number of new accounts Vasya puts into play, starting from 0. Then we can determine what solutions Vasya should submit from these accounts using the reasoning above. Then we can calculate the maximum point values of the problems, and then the number of points Vasya and Petya will score. If Vasya's score is higher than Petya's score, then the answer is x, otherwise we increase x by one and continue.
When do we stop? If Vasya submits solutions to a problem from the new accounts, then after putting at least n accounts into play the maximum point value of this problem will reach 500 and won't change anymore. If Vasya doesn't, then after putting at least 31n accounts into play the maximum point value of this problem will reach 3000 and won't change anymore. Therefore, if x exceeds 31n, we can stop and output -1.
Note that we can't find the value of x using binary search due to the fact that Vasya can't submit solutions to the problems he hasn't solved. That is, more accounts do not mean more profit. For example, consider the following test case:
If Vasya doesn't use any new accounts, his score will be 1000, while Petya's score will be 500. If Vasya uses at least 61 accounts, both his and Petya's score will be 3000.