Bessie가 북쪽 목장에서 뛰노는 레프러콘을 보고 얼마나 놀랐을지 상상하세요. 쉽게 속지 않는 그녀는 달려들어 움켜잡을 수 있는 발굽으로 잡았습니다.

“소야, 소원 하나다. 소에게 줄 수 있는 건 그뿐이야.” 그가 말했습니다.

“재물이요.” Bessie가 꿈꾸듯 말했습니다. “부자가 될 기회요.”

레프러콘은 자신을 잡은 자의 소원을 가장 쉬운 방식으로 이루어주지 않습니다. 큰 폭발의 연기가 걷히자 반짝이는 도넛이 푸른 들판 위에서 천천히 돌았습니다.

“너에게 토러스를 만들었어.” 그가 부드럽게 말했습니다. “위에는 $N\times N$ 행렬 $(1 \le N \le 200)$이 있고 정수 범위는 $-1{,}000{,}000,\ldots,1{,}000{,}000$으로 네 부의 크기를 정하지. 모든 가능한 수열 중 같은 행, 열, 대각선 하나의 연속 정수 수열로 가장 큰 합을 찾아야 해.”

Bessie는 잠시 생각하고 토러스가 행렬의 열, 행, 대각선을 “감아 이어” 옆이나 위 가장자리를 돌아가는 연속 원소를 고를 수 있게 함을 깨달았습니다.

Bessie가 행렬을 알려줍니다. 적어도 한 원소를 골라 가능한 최대 합을 구하세요.

예를 들어 아래 왼쪽 $4\times4$ 행렬은 돌아가는 대각선 한 예의 모든 원소를 표시했습니다.

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

오른쪽 표시된 대각선에는 9 두 개(가능한 가장 큰 수)와 6 하나가 있어 합이 24입니다. 최대 합이며 대각선의 네 원소 중 세 개만 포함합니다.

입력

• 줄 1: 정수 $N$ 하나입니다.
• 줄 $2,\ldots,N+1$: 줄 $i+1$에는 행렬의 $i$번째 행을 이루는 $N$개 정수가 공백으로 구분되어 있습니다.

출력

• 줄 1: 위 규칙에 따른 최대 합인 정수입니다.

예제

입력 1

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

출력 1

24

문제 출처: BOI'98에서 개작, 2008