동전 줍는 로봇 청소기

미르코는 박람회에서 똑똑한 로봇 청소기를 샀다. 성능을 시험해 보려고 판지로 상자를 만들고, 바닥을 $0$부터 $N$까지 번호를 붙인 $N+1$개의 행과 $N+1$개의 열로 나눴다. 그리고 바닥의 모든 칸에 동전을 몇 개씩 올려놨다. 네 모서리 칸 $(0, 0)$, $(0, N)$, $(N, 0)$, $(N, N)$에는 금화를 올려놨고, 나머지 칸에는 은화를 올려놨다.

청소기는 칸 $(0, 0)$에서 출발한다. 1초마다 이웃한 여덟 칸 중 하나로 움직이며, 상자 밖으로는 나갈 수 없다. 지나간 칸의 동전은 모두 주워지고, 같은 칸을 다시 지나면 그 칸에는 주울 동전이 남아 있지 않다. 출발하는 칸 $(0, 0)$의 동전도 처음에 주워진다.

미르코는 금화를 모두 줍고 은화는 최대한 많이 주운 다음, 정확히 $4N$초 만에 출발한 칸으로 돌아오라고 명령했다. 청소기가 주울 수 있는 동전 개수의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $N$이 주어진다. ($1 \le N \le 500$)

다음 $N+1$개 줄에는 상자 바닥의 한 행에 놓인 동전의 개수가 열 순서대로 $N+1$개씩 주어진다. 각 값은 $1$ 이상 $10000$ 이하이다.

청소기가 주울 수 있는 동전 개수의 최댓값을 한 줄에 출력한다.