위의 그림과 같이 삼각형 형태로 배치된 코스가 있는데, 맨위의 숫자에서 시작하여 한 층씩 이동하여 맨 아래 줄에 도착하는 경로를 탐색하려고 합니다. (예를들어, 위의 그림을 토대로, 처음 시작 층은 5, 다음 층은 1 5 입니다. 그리고 총 층 수는 5 입니다.)

바로 아래 숫자 혹은 오른쪽 아래 숫자로 내려갈 수 있다고 가정하고, 경로 중 포함된 숫자의 최대합을 찾는 프로그램을 작성하십시오.

입력

첫 줄에 총 층 수 ( 2 이상 100 이하 )

다음 줄 부터 삼각형의 각 가로줄에 들어가는 숫자 입력 ( 입력값 예시 참고)

출력

숫자의 최대합