레프러콘의 토러스

베시(Bessie)는 북쪽 목초지를 뛰노는 레프러콘(leprechaun)을 발견하고, 능숙한 앞발로 붙잡았습니다.

"소원 하나를 들어주지, 소야. 소에게 해줄 수 있는 건 그게 전부다." 레프러콘이 말했습니다.

"부(富)를 원해요." 베시가 꿈꾸듯 말했습니다.

레프러콘은 소원을 결코 가장 편한 형태로 들어주지 않습니다. 요란한 폭발의 연기가 걷히자, 반짝이는 도넛 모양의 물체가 푸른 들판 위로 천천히 돌고 있었습니다.

"토러스(torus, 도넛 모양)를 만들어 주었다." 레프러콘이 속삭였습니다. "그 토러스 위에는 크기가 $N \times N$ 인 정수 행렬이 놓여 있으며($1 \le N \le 200$), 각 원소는 $-1{,}000{,}000$ 이상 $1{,}000{,}000$ 이하의 정수다. 이 행렬이 너의 부(富)의 크기를 결정한다. 하나의 행, 하나의 열, 또는 하나의 대각선 위에서 연속한 정수들의 합이 가장 큰 구간을 찾아라."

행렬이 토러스(도넛) 위에 놓여 있으므로, 모든 행·열·대각선은 양 끝이 서로 이어져 순환합니다. 즉 어떤 선을 따라 연속한 원소들을 고를 때, 그 선의 한쪽 끝을 지나 반대쪽 끝으로 "감싸며" 계속 이어 고를 수 있습니다.

• 행: 같은 행의 원소들이 좌우로 순환합니다.
• 열: 같은 열의 원소들이 상하로 순환합니다.
• 대각선: 두 방향(↘ 방향과 ↙ 방향)의 대각선이 있으며, 각 대각선도 순환합니다. 토러스 위에서는 방향마다 정확히 $N$개의 대각선이 있고, 각 대각선은 서로 다른 원소 $N$개를 지납니다.

가능한 모든 구간(하나의 행, 열, 또는 대각선에서 연속한 원소들의 순환 구간이며 적어도 한 원소는 포함) 중에서 얻을 수 있는 가장 큰 합을 구하세요. 한 구간은 같은 원소를 두 번 포함하지 않으므로 원소를 최대 $N$개까지만 담을 수 있습니다.

예를 들어, 아래 $4 \times 4$ 행렬에서 ↙ 방향 대각선 하나(별표로 표시된 원소들)를 살펴봅시다.

 8  6* 6  1
-3  4  0  5
 4  2  1  9*
 1 -9  9*-2

이 대각선은 $(0,1)=6$, $(1,0)=-3$, $(2,3)=9$, $(3,2)=9$ 를 순환하며 지납니다(좌표는 0부터 시작하는 (행, 열)). 여기서 $-3$을 건너뛰고 $9$, $9$, $6$ 을 감싸며 이어 고르면 합이 $9+9+6=24$ 가 되어, 이 행렬에서 얻을 수 있는 최댓값이 됩니다.

• 첫째 줄: 정수 $N$.
• 둘째 줄부터 $N+1$째 줄까지: $i+1$째 줄에는 행렬의 $i$번째 행을 이루는 $N$개의 정수가 공백으로 구분되어 주어집니다.

• 위 규칙에 따라 얻을 수 있는 가장 큰 합을 나타내는 정수 하나를 출력합니다.