벌집 경로의 최대 합

그림 1은 숫자로 이루어진 벌집을 나타낸다(벌집의 한 변의 길이는 3이다). 경로는 가장 윗줄의 어떤 칸에서 시작하여 가장 아랫줄의 어떤 칸에서 끝난다. 한 칸에서 경로는 대각선 방향으로 왼쪽 아래 또는 오른쪽 아래로만 이어질 수 있다. 경로를 만들 때, 벌집의 가로줄 중 최대 한 줄에서 두 숫자를 최대 한 번 맞바꿀 수 있다. (맞바꾼다는 것은, 선택한 한 줄에서 그 줄의 가장 큰 숫자를 같은 줄의 원하는 위치로 옮길 수 있다는 뜻이다.) 이 맞바꾸기 능력을 사용하여, 어떤 경로가 지나는 숫자들의 합 중 가장 큰 값을 계산하는 프로그램을 작성하시오.

그림 1. 한 변의 길이가 3인 벌집.

첫째 줄에 벌집의 한 변의 길이 n이 주어진다. 벌집은 2n − 1개의 가로줄로 이루어진다. 이어지는 2n − 1개의 줄에 각 가로줄의 숫자들이 위에서부터 순서대로, 공백으로 구분되어 주어진다. 위에서 i번째 줄(1 ≤ i ≤ n)에는 n + i − 1개의 숫자가 있고, 가운데 줄을 지난 뒤로는 한 줄마다 숫자의 개수가 하나씩 줄어들어 가장 아랫줄에는 다시 n개의 숫자가 있다.

가장 큰 합을 정수 하나로 출력한다.

• 각 칸의 숫자는 0 이상 99 이하의 정수이다.
• 벌집의 한 변의 길이는 1 이상 99 이하의 정수이다.

그림 1에서 올바른 답(3 + 2 + 8 + 5 + 4 = 22)에 해당하는 칸들이 회색으로 칠해져 있다. 위에서 4번째 줄의 숫자 '5'가 그 줄의 왼쪽에서 3번째 위치로 옮겨진 것에 주목하라.