수들이 다이아몬드 형태로 배치되어 있을 때 각 가로줄에서 한 개씩의 루트를 따라서 맨 위칸에서 맨 아래칸으로 내려오는 경로를 찾고 싶습니다.

다음 칸으로 이동할 때는 인접한 수들로만 이동할 수 있습니다. 예를 들어 아래의 그림에서 2번째 줄의 4는 다음 줄의 7또는 9로 이동해야만 합니다.

경로에 포함된 숫자의 합이 가장 큰 경우의 값을 출력하는 프로그램을 작성하십시오.

입력

첫 줄에 다이아몬드 가운데 줄의 가로 길이( 3 이상 100 이하)

다음 줄부터 다이아몬드 각 가로줄에 속한 숫자 입력

출력

경로에 포함된 숫자의 합이 가장 큰 경우의 값