A10802 | Dynamic Problem Scoring

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.