#2016 사과 나무

68  1 s   128 MB  

Description

경희는 N * N 격자 형태의 사과 밭을 가지고 있다. 각 격자 칸에는 사과 나무가 존재할 수 있으며, 존재 할 경우 사과 나무에는 정확히 1개의 사과가 달려있을 수 있다.

경희는 또한 사과 나무를 추수하는 로봇을 가지고 있으며, 이를 이용해서 추수하려고 한다.

현재 로봇은 격자 내의 (1,1)에 위치에 있으며, 이곳 부터 추수를 시작한다. 만약 시작 위치를 포함한 이동한 위치의 사과 나무에 사과가 달려 있으면 달려 있는 개수 이하로 사과를 추수할 수 있다. 로봇은 현재 위치(x,y)에서 오른쪽(x+1,y) 혹은 아래(x,y+1) 쪽으로 움직일 수 있으며, 그 외의 방향의 움직임은 허용되지 않으며, 격자 밖을 벗어날 수 없으며, (N,N)에 도달할 경우 운행을 중단한다.

로봇은 추수한 사과를 들고 이동을 하게 되며, 더이상 움직이지 못할 때까지의 추수한 사과의 개수가 총 추수량이 된다.

추수량이 최대를 구하는 프로그램을 작성하라.

Input

입력의 첫 줄에는 사과 밭의 크기 N ( 3 ≤ N ≤ 100)가 주어진다.

다음 줄 부터 N행에 걸쳐 각 N개의 숫자가 입력된다. 이는 각 격자칸의 정보를 뜻하며 i번째 줄의 j번째 숫자가 1일 경우 좌표 (j,i)위치에 사과 나무가 달려있다는 것(다시 말해서 사과의 개수가 해당 칸에 1개가 있다는 것)을 뜻하고, 0일 경우에는 사과 나무가 존재하지 않음을 뜻한다.

Output

입력에 대해 최대 추수할 수 있는 사과의 개수를 출력하라.

Sample Input

Sample Output

5
0 1 0 0 1
0 0 1 0 0
1 0 1 1 0
1 1 0 1 0
1 0 0 0 1
6

HINT

최대 6개의 사과를 얻기위해서는 다음의 형태로 이동하면 된다.

0 1 0 0 1
0 0 1 0 0
1 0 1 1 0
1 1 0 1 0
1 0 0 0 1