남우는 나무를 잘 키워내 최대로 열매를 수확하려고 합니다. n×n 크기의 격자 내 각 칸에 씨앗이 정확히 하나씩 들어가 있고, 각 칸에 있는 씨앗을 키웠을 때 얻을 수 있는 열매 수확량이 주어집니다. 다음은 n이 3인 경우의 예시입니다.

씨앗을 키우기 위해서는 수로를 설치해야 합니다. 이때 비용 때문에 가장 좌측 위에 있는 (1, 1) 위치에서부터 수로 설치를 시작하여, 인접한 오른쪽 혹은 아래쪽 중 한곳을 선택하여 이동하여 정확히 (n, n) 위치를 끝으로 수로 설치를 마쳐야만 합니다. 예로 다음과 같이 수로 설치를 진행할 수 있습니다.

수로 설치가 완료되면 설치한 수로 중 원하는 칸 하나를 골라 그 위치에 스프링클러를 놓을 수 있습니다. 스프링클러가 놓인 칸의 경우 씨앗으로부터 얻을 수 있는 열매 수확량을 2배로 늘릴 수 있습니다. 만약 수로를 놓은 (1행, 3열)을 선택하게 된다면 다음과 같이 해당 칸의 열매 수확량이 6이 됩니다. 이렇게 수로와 스프링클러를 설치하게 되면 해당 칸들의 나무가 자라게 되어 최종적으로 얻게 되는 총 열매 수확량은 14(=1 + 3 + 6 + 3 + 1)가 됩니다.

만약 처음 그림에서 다음과 같이 수로와 스프링클러를 설치하게 되면, 총 15(=1+2+10+1+1)만큼 열매 수확을 할 수 있게 됩니다.

초기 격자의 상태가 주어졌을 때 수로와 스프링클러를 적절하게 설치하여 얻을 수 있는 열매 수확량의 합을 최대로 만드는 프로그램을 작성해보세요.

본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.