시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

바둑은 검은 돌과 흰 돌을 이용하여 진행하는 게임으로, 바둑판에 서로 번갈아가며 돌을 놓은 뒤, 집의 크기를 견주는 놀이이다. 바둑의 승패를 가리기 위해서는 이러한 집의 크기를 계산하는 것이 중요하다. 따라서 당신은 집의 크기를 계산하는 훈련을 하려 한다.

혼자 놀기에는 바둑판이 너무 크기 때문에, 우선 바둑판의 크기를 N(1≤N≤15)으로 한정한다. 따라서 바둑돌을 놓을 수 있는 위치는 N×N개가 된다. 또한 혼자 놀기 때문에 바둑판에는 검은 돌만을 놓는다고 하자. 이 때에는 바둑돌이 놓이지 않은 위치가 모두 집이 되는데, 따라서 이 문제에서는 검은 돌로 완전히 둘러싸인 부분만을 집으로 치기로 한다. 즉, 집은 다음의 조건을 만족하는 부분들을 말한다.

(1) 집인 위치에는 돌이 놓여있지 않다.
  (2) 바둑판의 테두리는 완전히 둘러싸일 수 없기 때문에 집이 아니다.
  (3) 집의 상하좌우는 집이거나 검은 돌이 놓여 있어야 한다.
  (4) 집이 아닌 곳의 상하좌우는 집이 아니다.

예를 들어서 아래와 같은 그림에서는 집의 크기가 3이 된다.

바둑판에 대한 정보가 주어졌을 때, 집의 크기를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N이 주어진다. 다음 줄에는 N개의 정수로, 위에서부터 아래로 각 행에 놓여 있는 돌의 개수가 주어진다. 다음 줄에는 N개의 정수로, 왼쪽부터 오른쪽까지 각 열에 놓여 있는 돌의 개수가 주어진다. 다음 줄에는 2×N-1개의 정수로, 왼쪽 위부터 오른쪽 아래까지, / 형태의 대각선 줄에 놓여있는 돌의 개수가 주어진다. 그 다음 줄에는 왼쪽 아래부터 오른쪽 위까지, \ 형태의 대각선 줄에 놓여있는 돌의 개수가 주어진다. 잘못된 입력은 주어지지 않으며, 항상 바둑판을 복원하는 방법이 유일한 경우만 입력으로 주어진다. 대각선은 45도의 대각선만 생각한다.

출력

첫째 줄에 집의 크기를 출력한다.

예제 입력

5
1 3 2 3 1
0 2 2 2 4
0 0 1 3 0 2 2 1 1
0 0 0 2 3 2 1 2 0

예제 출력

3

힌트