807_D. Dynamic Problem Scoring_28688
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.

<image>

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 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

Output a single integer — the number of new accounts Vasya needs to beat Petya, or -1 if Vasya can't achieve his goal.

Examples

Input

2
5 15 40 70 115
50 45 40 30 15


Output

2


Input

3
55 80 10 -1 -1
15 -1 79 60 -1
42 -1 13 -1 -1


Output

3


Input

5
119 119 119 119 119
0 0 0 0 -1
20 65 12 73 77
78 112 22 23 11
1 78 60 111 62


Output

27


Input

4
-1 20 40 77 119
30 10 73 50 107
21 29 -1 64 98
117 65 -1 -1 -1


Output

-1

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.
#include <bits/stdc++.h>
using namespace std;
long long point(long long a, long long b) {
  long long x = 500;
  while (x < 3000 and 2 * a <= b) {
    a *= 2;
    x += 500;
  }
  return x;
}
int main() {
  long long n, i, j, k;
  scanf("%lld", &n);
  long long arr[n + 1][5], count[5], score[5];
  memset(count, 0, sizeof count);
  for (i = 1; i <= n; i++) {
    for (j = 0; j < 5; j++) {
      scanf("%lld", &arr[i][j]);
      if (arr[i][j] == -1) {
        arr[i][j] = 250;
      } else {
        count[j]++;
      }
    }
  }
  for (i = 0; i <= 31 * n; i++) {
    double score_v = 0, score_p = 0;
    for (j = 0; j < 5; j++) {
      bool solved_v = 0, solved_p = 0;
      if (arr[1][j] != 250) solved_v = 1;
      if (arr[2][j] != 250) solved_p = 1;
      long long a = count[j], b = n + i, v = arr[1][j], p = arr[2][j];
      if (solved_v and solved_p and p < v) {
        a += i;
      }
      score[j] = point(a, b);
      score_v += (double)score[j] * (1 - (double)v / 250);
      score_p += (double)score[j] * (1 - (double)p / 250);
    }
    if (score_v > score_p) {
      printf("%lld\n", i);
      return 0;
    }
  }
  printf("-1\n");
  return 0;
}

2
5 15 40 70 115
50 45 40 30 15
 5
119 119 119 119 119
0 0 0 0 -1
20 65 12 73 77
78 112 22 23 11
1 78 60 111 62
 4
-1 20 40 77 119
30 10 73 50 107
21 29 -1 64 98
117 65 -1 -1 -1
 3
55 80 10 -1 -1
15 -1 79 60 -1
42 -1 13 -1 -1
 2
33 15 51 7 101
41 80 40 13 46
 2
0 0 0 0 1
0 0 0 1 0
 4
66 55 95 78 114
70 98 8 95 95
17 47 88 71 18
23 22 9 104 38
 17
66 15 -1 42 90
67 108 104 16 110
76 -1 -1 -1 96
108 32 100 91 17
87 -1 85 10 -1
70 55 102 15 23
-1 33 111 105 63
-1 56 104 68 116
56 111 102 89 63
63 -1 68 80 -1
80 61 -1 81 19
101 -1 87 -1 89
92 82 4 105 83
19 30 114 77 104
100 99 29 68 82
98 -1 62 52 -1
108 -1 -1 50 -1
 9
57 52 60 56 91
32 40 107 89 36
80 0 45 92 119
62 9 107 24 61
43 28 4 26 113
31 91 86 13 95
4 2 88 38 68
83 35 57 101 28
12 40 37 56 73
 3
20 65 12 73 77
78 112 22 23 11
1 78 60 111 62
 10
-1 18 44 61 115
-1 34 12 40 114
-1 86 100 119 58
-1 4 36 8 91
1 58 85 13 82
-1 9 85 109 -1
13 75 0 71 42
116 75 42 79 88
62 -1 98 114 -1
68 96 44 61 35
 26
3 -1 71 -1 42
85 72 48 38 -1
-1 -1 66 24 -1
46 -1 60 99 107
53 106 51 -1 104
-1 17 98 54 -1
44 107 66 65 102
47 40 62 34 5
-1 10 -1 98 -1
-1 69 47 85 75
12 62 -1 15 -1
48 63 72 32 99
91 104 111 -1 -1
92 -1 52 -1 11
118 25 97 1 108
-1 61 97 37 -1
87 47 -1 -1 21
79 87 73 82 70
90 108 19 25 57
37 -1 51 8 119
64 -1 -1 38 82
42 61 63 25 27
82 -1 15 82 15
-1 89 73 95 -1
4 8 -1 70 116
89 21 65 -1 88
 19
78 100 74 31 2
27 45 72 63 0
42 114 31 106 79
88 119 118 69 90
68 14 90 104 70
106 21 96 15 73
75 66 54 46 107
108 49 17 34 90
76 112 49 56 76
34 43 5 57 67
47 43 114 73 109
79 118 69 22 19
31 74 21 84 79
1 64 88 97 79
115 14 119 101 28
55 9 43 67 10
33 40 26 10 11
92 0 60 14 48
58 57 8 12 118
 2
27 15 51 7 101
41 80 40 13 46
 4
66 55 95 78 114
70 98 8 95 95
17 47 88 71 18
7 22 9 104 38
 17
66 15 -1 42 90
67 108 104 16 110
76 -1 -1 -1 96
108 32 100 91 17
87 -1 85 10 -1
70 55 102 15 23
-1 33 111 105 63
-1 56 104 68 116
56 111 102 89 63
63 -1 68 80 -1
80 61 -1 81 19
001 -1 87 -1 89
92 82 4 105 83
19 30 114 77 104
100 99 29 68 82
98 -1 62 52 -1
108 -1 -1 50 -1
 9
57 52 60 56 91
32 40 107 89 36
80 0 45 92 119
62 12 107 24 61
43 28 4 26 113
31 91 86 13 95
4 2 88 38 68
83 35 57 101 28
12 40 37 56 73
 3
20 65 12 73 77
78 112 22 23 0
1 78 60 111 62
 10
-1 18 44 61 115
-1 34 12 40 114
-1 86 100 119 58
-1 4 36 8 91
1 58 85 13 82
-1 9 85 109 -1
13 75 0 71 42
116 75 42 79 88
62 -1 98 114 -1
47 96 44 61 35
 26
3 -1 71 -1 42
85 72 48 38 -1
-1 -1 66 24 -1
46 -1 60 99 107
53 106 51 -1 104
-1 17 135 54 -1
44 107 66 65 102
47 40 62 34 5
-1 10 -1 98 -1
-1 69 47 85 75
12 62 -1 15 -1
48 63 72 32 99
91 104 111 -1 -1
92 -1 52 -1 11
118 25 97 1 108
-1 61 97 37 -1
87 47 -1 -1 21
79 87 73 82 70
90 108 19 25 57
37 -1 51 8 119
64 -1 -1 38 82
42 61 63 25 27
82 -1 15 82 15
-1 89 73 95 -1
4 8 -1 70 116
89 21 65 -1 88
 19
78 100 74 31 2
27 45 72 63 1
42 114 31 106 79
88 119 118 69 90
68 14 90 104 70
106 21 96 15 73
75 66 54 46 107
108 49 17 34 90
76 112 49 56 76
34 43 5 57 67
47 43 114 73 109
79 118 69 22 19
31 74 21 84 79
1 64 88 97 79
115 14 119 101 28
55 9 43 67 10
33 40 26 10 11
92 0 60 14 48
58 57 8 12 118
 2
5 15 40 70 115
3 45 40 30 15
 4
-1 20 40 77 119
30 10 73 50 194
21 29 -1 64 98
117 65 -1 -1 -1
 17
66 15 -1 42 90
67 108 104 16 110
76 -1 -1 -1 96
108 32 100 91 17
87 -1 85 10 -1
70 55 102 15 23
-1 33 111 105 63
-1 56 104 68 116
56 111 102 89 63
63 0 68 80 -1
80 61 -1 81 19
001 -1 87 -1 89
92 82 4 137 83
19 30 114 77 104
100 99 29 68 82
98 -1 62 52 -1
108 -1 -1 50 -1
 10
-1 18 34 61 115
-1 34 12 40 114
-1 86 100 119 58
-1 4 36 8 91
1 58 85 13 82
-1 9 85 109 -1
24 75 0 71 42
116 75 42 79 88
62 -1 105 114 -1
47 96 44 61 28
 2
0 0 0 0 1
0 0 0 1 -1
 5
119 119 119 119 119
0 0 -1 0 -1
20 65 12 73 77
78 112 22 23 11
1 78 60 111 62
 3
55 80 10 -1 -1
15 -1 79 117 -1
42 -1 13 -1 -1
 2
15 15 51 7 101
41 80 40 13 46
 2
0 0 0 0 1
0 -1 0 1 -1
 4
66 55 95 78 114
70 98 13 95 95
17 47 88 71 18
7 22 9 104 38
 17
66 15 -1 42 90
67 108 104 16 110
76 -1 -1 -1 96
108 32 100 91 17
87 -1 85 10 -1
70 55 102 15 23
-1 33 111 105 63
-1 56 104 68 116
56 111 102 89 63
63 -1 68 80 -1
80 61 -1 81 19
001 -1 87 -1 89
92 82 4 137 83
19 30 114 77 104
100 99 29 68 82
98 -1 62 52 -1
108 -1 -1 50 -1
 9
57 52 60 56 91
32 40 107 89 36
80 0 45 92 119
62 12 107 24 61
43 28 4 26 113
31 91 23 13 95
4 2 88 38 68
83 35 57 101 28
12 40 37 56 73
 3
20 65 12 73 77
78 112 22 23 0
1 78 60 110 62
 10
-1 18 44 61 115
-1 34 12 40 114
-1 86 100 119 58
-1 4 36 8 91
1 58 85 13 82
-1 9 85 109 -1
13 75 0 71 42
116 75 42 79 88
62 -1 105 114 -1
47 96 44 61 35
 26
3 -1 71 -1 42
85 72 48 38 -1
-1 -1 66 24 -1
46 -1 60 99 107
53 106 51 -1 104
-1 17 135 54 -1
44 107 66 65 102
47 40 62 34 5
-1 10 -1 98 -1
-1 69 47 85 75
12 62 -1 15 -1
48 63 72 32 99
91 104 111 -1 -1
92 -1 52 -1 11
118 25 97 1 108
-1 78 97 37 -1
87 47 -1 -1 21
79 87 73 82 70
90 108 19 25 57
37 -1 51 8 119
64 -1 -1 38 82
42 61 63 25 27
82 -1 15 82 15
-1 89 73 95 -1
4 8 -1 70 116
89 21 65 -1 88
 19
78 100 74 31 2
27 45 72 63 1
42 114 31 106 79
88 119 118 69 90
68 14 90 104 70
106 21 96 15 73
75 66 54 46 107
108 49 17 48 90
76 112 49 56 76
34 43 5 57 67
47 43 114 73 109
79 118 69 22 19
31 74 21 84 79
1 64 88 97 79
115 14 119 101 28
55 9 43 67 10
33 40 26 10 11
92 0 60 14 48
58 57 8 12 118
 2
3 15 40 70 115
3 45 40 30 15
 5
119 119 119 119 119
0 1 -1 0 -1
20 65 12 73 77
78 112 22 23 11
1 78 60 111 62
 4
-1 20 40 77 119
30 10 73 22 194
21 29 -1 64 98
117 65 -1 -1 -1
 3
55 80 10 -1 -1
15 -1 79 62 -1
42 -1 13 -1 -1
 2
16 15 51 7 101
41 80 40 13 46
 2
0 0 0 -1 1
0 -1 0 1 -1
 4
66 55 95 78 114
70 98 13 95 95
17 47 88 71 18
7 36 9 104 38
 9
57 52 60 56 91
32 40 107 89 36
80 0 45 92 119
62 12 107 24 61
43 28 4 26 113
31 91 23 13 95
4 2 88 38 68
83 35 57 101 28
12 40 54 56 73
 3
20 65 12 73 77
78 112 39 23 0
1 78 60 110 62
 10
-1 18 44 61 115
-1 34 12 40 114
-1 86 100 119 58
-1 4 36 8 91
1 58 85 13 82
-1 9 85 109 -1
13 75 0 71 42
116 75 42 79 88
62 -1 105 114 -1
47 96 44 61 28
 26
3 -1 71 -1 42
85 72 48 38 -1
-1 -1 66 24 -1
46 -1 60 99 107
53 106 51 -1 104
-1 17 135 54 -1
44 107 66 65 102
47 40 62 34 5
-1 10 -1 98 -1
-1 69 47 85 75
12 62 -1 15 -1
48 63 72 32 99
116 104 111 -1 -1
92 -1 52 -1 11
118 25 97 1 108
-1 78 97 37 -1
87 47 -1 -1 21
79 87 73 82 70
90 108 19 25 57
37 -1 51 8 119
64 -1 -1 38 82
42 61 63 25 27
82 -1 15 82 15
-1 89 73 95 -1
4 8 -1 70 116
89 21 65 -1 88
 19
78 100 74 31 2
27 45 72 63 1
42 114 31 106 79
88 119 118 69 90
68 14 90 104 70
106 21 96 15 73
75 66 54 46 107
108 49 17 48 90
76 112 49 56 76
34 43 5 57 67
47 43 114 111 109
79 118 69 22 19
31 74 21 84 79
1 64 88 97 79
115 14 119 101 28
55 9 43 67 10
33 40 26 10 11
92 0 60 14 48
58 57 8 12 118
 2
4 15 40 70 115
3 45 40 30 15
 5
119 187 119 119 119
0 1 -1 0 -1
20 65 12 73 77
78 112 22 23 11
1 78 60 111 62
 4
-1 20 40 77 119
30 10 73 22 194
21 37 -1 64 98
117 65 -1 -1 -1
 2
16 15 79 7 101
41 80 40 13 46
 2
0 -1 0 -1 1
0 -1 0 1 -1
 4
66 55 95 78 114
70 98 13 126 95
17 47 88 71 18
7 36 9 104 38
 17
66 15 -1 42 90
67 108 104 16 110
76 -1 -1 -1 96
108 32 100 91 17
87 -1 85 10 -1
70 55 102 15 23
0 33 111 105 63
-1 56 104 68 116
56 111 102 89 63
63 0 68 80 -1
80 61 -1 81 19
001 -1 87 -1 89
92 82 4 137 83
19 30 114 77 104
100 99 29 68 82
98 -1 62 52 -1
108 -1 -1 50 -1
 9
57 52 60 56 91
32 40 107 89 36
80 0 45 92 119
62 12 107 24 61
43 28 4 26 113
31 91 23 13 95
4 2 70 38 68
83 35 57 101 28
12 40 54 56 73
 3
20 65 12 117 77
78 112 39 23 0
1 78 60 110 62
 10
-1 18 44 61 115
-1 34 12 40 114
-1 86 100 119 58
-1 4 36 8 91
1 58 85 13 82
-1 9 85 109 -1
24 75 0 71 42
116 75 42 79 88
62 -1 105 114 -1
47 96 44 61 28
 26
3 -1 71 -1 42
85 72 48 38 -1
-1 -1 66 24 -1
46 -1 60 99 107
53 106 51 -1 104
-1 17 135 54 -1
44 107 66 65 102
47 40 62 34 5
-1 10 -1 98 -1
-1 69 47 85 75
12 62 -1 15 -1
48 63 72 32 99
116 104 111 -1 -1
92 -1 52 -1 5
118 25 97 1 108
-1 78 97 37 -1
87 47 -1 -1 21
79 87 73 82 70
90 108 19 25 57
37 -1 51 8 119
64 -1 -1 38 82
42 61 63 25 27
82 -1 15 82 15
-1 89 73 95 -1
4 8 -1 70 116
89 21 65 -1 88
 19
78 100 74 31 2
27 45 72 63 1
42 114 31 106 79
88 119 118 69 90
68 14 90 104 70
93 21 96 15 73
75 66 54 46 107
108 49 17 48 90
76 112 49 56 76
34 43 5 57 67
47 43 114 111 109
79 118 69 22 19
31 74 21 84 79
1 64 88 97 79
115 14 119 101 28
55 9 43 67 10
33 40 26 10 11
92 0 60 14 48
58 57 8 12 118
 2
4 15 56 70 115
3 45 40 30 15
 5
119 187 119 119 119
0 1 -1 0 -1
6 65 12 73 77
78 112 22 23 11
1 78 60 111 62
 4
-1 20 40 77 119
30 10 73 22 194
21 37 -1 25 98
117 65 -1 -1 -1
 2
16 15 79 7 101
74 80 40 13 46
 2
0 -1 0 -1 1
-1 -1 0 1 -1
 4
66 55 95 78 114
70 98 13 171 95
17 47 88 71 18
7 36 9 104 38
 9
57 52 60 56 93
32 40 107 89 36
80 0 45 92 119
62 12 107 24 61
43 28 4 26 113
31 91 23 13 95
4 2 70 38 68
83 35 57 101 28
12 40 54 56 73
 3
20 65 12 117 18
78 112 39 23 0
1 78 60 110 62
 26
3 -1 71 -1 42
85 72 48 38 -1
-1 -1 66 24 -1
46 -1 60 99 107
53 106 51 -1 104
-1 17 135 54 -1
44 107 66 65 102
47 40 62 34 5
-1 10 -1 98 -1
-1 69 47 85 75
12 62 -1 15 -1
48 63 72 32 99
116 104 111 -1 -1
92 -1 52 -1 5
118 25 97 1 108
-1 78 97 37 -1
87 47 -1 -1 21
79 87 73 82 70
90 108 22 25 57
37 -1 51 8 119
64 -1 -1 38 82
42 61 63 25 27
82 -1 15 82 15
-1 89 73 95 -1
4 8 -1 70 116
89 21 65 -1 88
 19
78 100 74 31 2
27 45 72 63 1
42 114 31 106 79
88 119 118 69 90
68 14 90 104 70
93 21 96 15 73
75 66 54 46 107
108 49 17 48 90
76 112 49 56 76
34 43 5 57 67
47 43 114 011 109
79 118 69 22 19
31 74 21 84 79
1 64 88 97 79
115 14 119 101 28
55 9 43 67 10
33 40 26 10 11
92 0 60 14 48
58 57 8 12 118
 2
4 15 56 70 152
3 45 40 30 15
 5
119 187 119 119 119
0 1 -1 0 -1
6 65 12 73 77
78 112 22 23 11
0 78 60 111 62
 4
-1 20 40 123 119
30 10 73 22 194
21 37 -1 25 98
117 65 -1 -1 -1
 2
16 27 79 7 101
74 80 40 13 46
 2
-1 -1 0 -1 1
-1 -1 0 1 -1
 4
66 55 95 78 114
70 113 13 171 95
17 47 88 71 18
7 36 9 104 38
 9
57 52 60 56 93
32 40 107 89 36
80 0 45 92 119
62 12 107 24 61
43 28 4 26 113
31 91 23 13 95
4 2 70 38 68
83 16 57 101 28
12 40 54 56 73
 3
20 65 12 117 18
78 112 39 19 0
1 78 60 110 62

2
 27
 -1
 3
 0
 2
 4
 5
 9
 3
 62
 10
 133
 0
 4
 5
 9
 3
 62
 10
 133
 30
 -1
 7
 26
 0
 3
 0
 0
 0
 4
 5
 9
 3
 62
 10
 133
 30
 3
 -1
 3
 0
 0
 4
 9
 0
 62
 10
 133
 30
 3
 -1
 0
 -1
 4
 7
 9
 3
 62
 10
 133
 62
 3
 -1
 0
 0
 0
 9
 0
 10
 133
 -1
 3
 -1
 0
 -1
 0
 9
 0
