조약돌 | cho.sh

문제

$N \times N$ 크기의 게임판에 조약돌을 원하는 만큼 놓을 수 있습니다. 여기서 $3 \le N \le 15$ 입니다. 각 칸에는 $10$ 이상 $99$ 이하의 양의 점수가 하나씩 적혀 있습니다. 예를 들어 $6 \times 6$ 게임판은 다음과 같이 생겼을 수 있습니다.


33	74	26	55	79	54
67	56	91	72	44	32
44	64	22	91	29	61
61	32	76	50	50	32
81	65	56	38	96	36
38	78	50	92	90	75

다음 두 규칙을 지키며 조약돌을 놓습니다.

한 칸에는 조약돌을 최대 한 개만 놓을 수 있습니다.
서로 인접한 두 칸에 동시에 조약돌을 놓을 수 없습니다. 두 칸은 가로, 세로, 또는 대각선으로 맞닿아 있으면 인접한 것으로 봅니다.

게임판은 반대쪽 끝과 이어지지 않으므로, 같은 행이나 열의 양쪽 끝 칸, 그리고 서로 멀리 떨어진 두 모서리 칸은 인접하지 않습니다.

점수는 조약돌이 놓인 모든 칸의 점수를 합한 값입니다. 이 점수를 최대로 만드세요.

입력에는 여러 개의 게임판이 들어올 수 있으며, 각 게임판마다 얻을 수 있는 최대 점수를 구합니다.

입력

각 게임판은 $N$개의 줄로 이루어지며, 한 줄에는 공백으로 구분된 $N$개의 점수(칸마다 하나씩)가 들어 있습니다. 게임판 사이는 빈 줄로 구분됩니다. 입력이 끝날 때까지 게임판을 계속 읽습니다.

출력

각 게임판마다 규칙을 지키며 얻을 수 있는 최대 점수를 정수 하나로 한 줄에 출력합니다.


33	74	26	55	79	54
67	56	91	72	44	32
44	64	22	91	29	61
61	32	76	50	50	32
81	65	56	38	96	36
38	78	50	92	90	75


33	74	26	55	79	54
67	56	91	72	44	32
44	64	22	91	29	61
61	32	76	50	50	32
81	65	56	38	96	36
38	78	50	92	90	75


33	74	26	55	79	54
67	56	91	72	44	32
44	64	22	91	29	61
61	32	76	50	50	32
81	65	56	38	96	36
38	78	50	92	90	75