월드컵 조별리그

FIFA가 주관하는 월드컵은 4년마다 열린다. 2022년 카타르 월드컵을 기준으로 참가팀은 4팀씩 조에 편성되고, 같은 조의 팀끼리 한 번씩 경기한다. 조별리그에서는 1위와 2위만 토너먼트에 진출한다. 조별리그 순위는 다음 순서로 정한다.

1. 승점: 승점이 큰 팀이 위에 있다. 승점은 경기 결과에 따라 정해진다. 승리 시 3점, 무승부 시 1점, 패배 시 0점이다.
2. 골득실: (득점 - 실점)이 큰 팀이 위에 있다.
3. 다득점: 가장 많은 득점을 한 팀이 위에 있다.
4. 상대 전적: 편성된 조에서 상대 전적 순위가 더 높은 팀이 위에 있다.

먼저 승점으로 순위를 정한다. 승점이 같으면 골득실로, 골득실도 같으면 다득점으로 가린다. 다득점까지 같으면 상대 전적 순위로 정한다.

A, B, C, D 팀이 한 조에 편성되었다. 상대 전적 순위는 항상 A팀이 1위, B팀이 2위, C팀이 3위, D팀이 4위이다. 모든 경기가 끝나면 각 경기에서 팀이 득점한 수를 적은 득점표가 주어진다.

$W_{ij}$는 i팀이 j팀을 상대로 득점한 값이다. 바꿔 말하면 $W_{ij}$는 j팀이 i팀을 상대로 실점한 값이기도 하다.

표 1

득점표로 경기 결과를 알 수 있다. A팀과 B팀의 경기 결과를 알고 싶으면 "A팀" 행의 "(B팀)" 열과 "B팀" 행의 "(A팀)" 열을 보면 된다. 결과는 2:0으로 A팀의 승리다.

A팀과 D팀의 경기에서는 D팀의 득점이 누락되어 $?$로 적혀 있다. D팀이 토너먼트에 진출하려면 A팀을 상대로 최소 2점을 득점해야 한다.

이처럼 팀 $T$의 득점 하나가 누락된 득점표가 주어질 때, 팀 $T$가 진출할 수 있는 $?$의 최솟값을 구하시오. 단, $?$ 값과 관계없이 $T$가 진출할 수 없으면 -1을 출력한다.

첫 번째 줄에 팀 $T$의 상대 전적 순위와 양의 정수 $K$가 공백으로 구분되어 주어진다.

두 번째 줄부터 4개의 줄에 걸쳐 득점표가 주어진다. 각 줄에는 득점 $W_{ij}$가 공백으로 구분되어 주어진다.

• $i=j$인 경우 0으로 주어진다.
• $i \neq j$인 경우
  • 누락되지 않은 득점은 음이 아닌 정수로 주어진다.
  • 누락된 득점 $?$는 -1로 주어진다.

두 번째 줄은 A팀, 세 번째 줄은 B팀, 네 번째 줄은 C팀, 다섯 번째 줄은 D팀의 득점이다.

주어지는 득점표에는 누락된 득점이 항상 1개이며, 팀 $T$는 항상 한 경기에서 득점이 누락되어 있다.

팀 $T$가 진출할 수 있는 득점 $?$의 최솟값을 출력한다.

단, 최솟값이 $K$보다 크거나, $?$ 값과 관계없이 $T$가 진출할 수 없으면 -1을 출력한다.

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