Dynamic Problem Scoring_信奥算法普及/提高--ACGO题库

题目描述

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

输出格式

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.

输入输出样例

输入#1
```
2
5 15 40 70 115
50 45 40 30 15
```
输出#1
```
2
```

输入#2

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

输出#2

输入#3

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

输出#3

输入#4

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

输出#4

-1

说明/提示