World Cup Group Stage

The FIFA World Cup is held every four years. Starting with the 2022 Qatar World Cup, teams are divided into groups of four, and each team plays every other team in its group once. Only the top two teams in each group advance to the knockout stage. Group standings are decided by the following criteria, in order:

1. Points: the team with more points ranks higher. Points depend on the match results: 3 for a win, 1 for a draw, 0 for a loss.
2. Goal difference: the team with a larger (goals scored - goals conceded) ranks higher.
3. Goals scored: the team that scored the most goals ranks higher.
4. Head-to-head: the team with the higher head-to-head rank in the group ranks higher.

Standings are sorted by points first. If points are tied, goal difference decides. If goal difference is also tied, goals scored decides. If that is tied too, head-to-head rank decides.

Teams A, B, C, and D are placed in one group. Their head-to-head ranks are always A first, B second, C third, and D fourth. After all matches, a score table shows how many goals each team scored in each match.

$W_{ij}$ is the number of goals team $i$ scored against team $j$. Equivalently, $W_{ij}$ is the number of goals team $j$ conceded against team $i$.

Table 1

The result of any match can be read from the table. To find the result of Team A against Team B, check row Team A, column (Team B), and row Team B, column (Team A). Here the result is 2:0, a win for Team A.

In the match between Team A and Team D, Team D's score is missing and is marked $?$. Team D must score at least 2 goals against Team A to advance.

Given a score table where one score of team $T$ is missing, find the minimum value of $?$ that lets team $T$ advance. If team $T$ cannot advance regardless of the value of $?$, print -1.

The first line contains the head-to-head rank of team $T$ and a positive integer $K$, separated by a space.

The next 4 lines contain the score table. Each line contains the scores $W_{ij}$ separated by spaces.

• If $i=j$, the value is given as 0.
• If $i \neq j$:
  • A score that is not missing is given as a non-negative integer.
  • The missing score $?$ is given as -1.

The second line is the scores of Team A, the third line Team B, the fourth line Team C, and the fifth line Team D.

The score table always has exactly one missing score, and team $T$ always has a missing score in one of its matches.

Print the minimum value of $?$ that lets team $T$ advance.

However, if the minimum is greater than $K$, or if team $T$ cannot advance regardless of the value of $?$, print -1.

• $1\,000 \le K \le 10^{12}$
• $0 \le W_{ij} \le K$