동전 줍는 로봇 청소기

시간 제한4초메모리 제한128 MB

요약

진공청소기가 (N+1)x(N+1) 격자에서 4N초 동안 이동하며 네 모서리 금화를 모두 주우면서 모은 동전 수를 최대로 만드는 값을 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

미르코는 박람회에서 똑똑한 로봇 청소기를 샀다. 성능을 시험해 보려고 판지로 상자를 만들고, 바닥을 $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$ 이하이다.

출력

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

예제2

예제 1
입력
```
2
1 1 1
1 10 1
1 1 1
```
예상 출력
```
17
```
예제 2
입력
```
3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
```
예상 출력
```
51
```