그림 1 은 크기 3 인 벌집이다.

윗 헹에서 시작하여 아래 행에서 끝나야 한다. 길은 대각선 왼쪽이나 오른쪽으로 선택해서 갈수 있다. 길을 따라 갈 때 많아야 한 번 한 행에 있는 수를 교체 할 수 있다. (교체 한 다는 말은 그 행 중에 있는 최대값과 길 위에 있는 수를 교체할 수 있다는 의미이다)

이런 능력을 가지고 찾을 수 있는 최대 합을 출력하는 게 문제이다.

크기 3 인 벌집

제한

• 각 노드에 있는 수는 0 이상 99 이하의 정수이다.
• 벌집의 크기는 1 이상 99 이하인 정수이다.

입력형식

• 첫 행에서는 벌집의 크기 n 이 주어진다.
• 다음 2n-1 개의 줄에는 벌집의 정보가 주어진다.

출력형식

입출력 예

입력

3
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4

출력

22

출처:boi 
추천:CONANKUN