미술관에 액자 배치하기

미술관장인 홍박사는 그의 미술관에 액자들을 배치하려고 합니다. 

액자를 걸 빈 공간은 $N \times N$ 격자의 정사각형 셀들로 표현할 수 있습니다. ($2 \leq N \leq 1000$), 빈 공간은 마치 $N \times N$ 체스판처럼 생겼습니다. 

마지막에 미술관장이 배치한 액자들은 공간의 한 곳에 너무 몰려있었습니다. 그는 액자들이 빈 공간 전체에 고르고 배치되도록 하고 싶어합니다.

이를 위해 다음 규칙을 따라서 배치해야합니다.

• 두 액자는 같은 셀에 놓여서는 안 됩니다.
• 모든 $2 \times 2$ 셀의 부분 격자는 정확히 두 개의 액자를 포함해야 합니다. 총 $(N-1) \times (N-1)$ 개의 부분 격자가 있습니다.

예를 들어 아래 배치는 가능합니다.

CCC
...
CCC

아래 배치는 불가능합니다. 왜냐하면 오른쪽 아래에 모서리 셀을 포함하는 $2 \times 2$ 정사각형 영역 안에 액자가 오직 하나만 있기 때문입니다:

C.C
.C.
C..

다른 제약 사항은 없습니다. 미술관장은 무한한 수의 액자를 가지고 있다고 가정할 수 있습니다.

미술관장은 일부 셀에는 다른 셀보다 더 많은 액자가 있길 원합니다. 특히 셀 $(i, j)$에 액자가 배치되면 사진의 매력값이 $a_{ij}$ ($0 \leq a_{ij} \leq 1000$) 단위만큼 증가한다고 생각합니다.

액자들을 잘 배치했을 때, 가능한 사진의 최대 매력값을 구하시오.

첫번째 줄은 $N$를 포함합니다. 다음 $N$ 줄은 $N$ 개의 정수를 각각 포함합니다. 위에서 $i$번째 줄의 $j$번째 정수는 $a_{ij}$의 값입니다.

가능한 사진의 최대 매력값을 나타내는 한 개의 정수를 출력하세요.