마시멜로우

가로 , 세로 크기 격자의 각 칸에 몇 개씩의 마시멜로가 들어 있다. 제일 왼쪽 위 칸에서 제일 오른쪽 아래 칸으로 가면서 지나가는 칸들에서 마시멜로를 모으려고 한다. 단, 이동하는 것은 현재 칸에서 바로 오른쪽 혹은 바로 아래쪽 칸으로만 가능하다.

오른쪽 프로그램을 채워 봅시다.

오른쪽 코드에서 A에는 입력 값들이 저장되어 있고, B는 A와 동일한 크기의 배열인데 B[n][n]의 값이 최종 답이 될 것이다.

참고 사항

max(P, Q) 함수는 P와 Q 중 더 큰 값을 리턴하는 함수이다.

입력 형식

프로그램의 입력 첫 줄에는 격자의 크기 이 주어진다. 다음 개의 줄 각각에는 격자의 한 행의 칸들에 있는 마시멜로의 개수가 주어진다.

은 1 이상 1000 이하이다. 각 칸의 마시멜로 개수는 1 이상 100 이하의 정수이다.

프로그램은 모을 수 있는 가장 많은 마시멜로의 개수를 출력한다.

예제

입력

4
1 3 2 1
1 2 1 2
1 1 2 1
3 1 2 1

출력

12