시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB129484037.037%

문제

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$위이다. 모든 경기를 치른 후, 팀이 각 경기에서 얼마나 득점했는지 알려주는 득점표가 주어진다.

득점표 (A팀) (B팀) (C팀) (D팀)
A팀 - $W_{AB}$ $W_{AC}$ $W_{AD}$
B팀 $W_{BA}$ - $W_{BC}$ $W_{BD}$
C팀 $W_{CA}$ $W_{CB}$ - $W_{CD}$
D팀 $W_{DA}$ $W_{DB}$ $W_{DC}$ -

<득점표>

득점표에서 $W_{ij}$는 $i$팀이 $j$팀 상대로 득점한 값을 의미한다. 반대로 말해서 $W_{ij}$는 $j$팀이 $i$팀 상대로 실점한 값을 의미한다.

득점표 (A팀) (B팀) (C팀) (D팀)
A팀 0 2 3 1
B팀 0 0 2 0
C팀 2 0 0 3
D팀 $?$ 0 2 0

<표 1>

<표 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$ 인 경우
    • $W_{ij}$가 누락되지 않은 득점일 경우 음이 아닌 정수로 주어진다.
    • $W_{ij}$가 누락된 득점 $?$일 경우 -1로 주어진다.

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

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

출력

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

단, 최솟값이 $K$보다 크거나 득점 $?$값과 상관없이 진출 자격을 획득할 수 없으면 -1을 출력한다.

제한

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

서브태스크

번호배점제한
110

$K=1\,000$

290

추가적인 제약 조건이 없다.

예제 입력 1

4 1000
0 2 3 1
0 0 2 0
2 0 0 3
-1 0 2 0

예제 출력 1

2

다득점으로 진출한다. 예제 1은 2022 카타르 월드컵 H조를 참고했다.

예제 입력 2

4 1000
0 2 1 2
0 0 2 3
1 1 0 2
-1 1 0 0

예제 출력 2

-1

득점 $?$값과 상관없이 진출 자격을 획득할 수 없다. 예제 2는 2022 카타르 월드컵 A조를 참고했다.

예제 입력 3

2 1000
0 2 1 0
1 0 1 -1
1 0 0 1
1 0 0 0

예제 출력 3

0

상대 전적으로 진출한다. 예제 3은 1994 미국 월드컵 E조를 참고했다.

예제 입력 4

1 1000
0 -1 1 1
0 0 5 3
0 0 0 2
0 1 1 0

예제 출력 4

0

승점으로 진출한다. 예제 4는 2018 러시아 월드컵 A조를 참고했다.

채점 및 기타 정보

  • 예제는 채점하지 않는다.