소들의 파친코

소들이 파친코라는 게임을 하고 있습니다. 위에서 공을 떨어뜨리면 아래로 내려가면서 못에 부딪히고, 좌우로 조금씩 방향을 틀며 맨 아래로 나옵니다.

이 파친코는 특별합니다. 공은 항상 $R$개의 못 줄 중 맨 위 못에 먼저 부딪힙니다 ($1 \le R \le 25$). 그다음에는 바로 아래의 왼쪽 또는 오른쪽 못에 부딪힙니다. 여기서 다시 바로 아래의 왼쪽 또는 오른쪽 못으로 내려가며, 이 과정을 맨 아래 줄까지 반복합니다. 공은 방금 부딪힌 못에서 너무 멀리(못 반 칸을 넘게) 벗어나지 않습니다.

이 게임의 점수 계산도 독특합니다. 내려오는 길에 부딪히는 못마다 점수 $X_{ij}$ ($0 \le X_{ij} \le 3000$)를 얻습니다. 소들은 이 기계에서 점수를 최대로 만들고 싶어 합니다. 얻을 수 있는 가장 높은 점수는 얼마일까요?

다음은 삼각형과 좋은 경로의 예시입니다. 별표(*)로 표시된 못들이 공이 지나가는 경로입니다.

                    7                        *7
                  3   8                    *3   8
                8   1   0                *8   1   0
              2   7   4   4             2  *7   4   4
            4   5   2   6   5         4  *5   2   6   5

위 예시에서 $7 \to 3 \to 8 \to 7 \to 5$ 경로가 합 $30$으로 가장 높습니다. $7$에서 $8$로, 다시 $8$로 가는 것은 불가능합니다. 셋째 줄의 $8$은 너무 멀리 떨어져 있기 때문입니다.

• 첫째 줄: 정수 $R$.
• 둘째 줄부터 $R+1$째 줄까지: $i+1$째 줄에는 기계의 $i$번째 줄 점수 $X_{i1}, X_{i2}, \dots, X_{ii}$가 공백으로 구분되어 주어집니다($i$개의 정수).

• 첫째 줄: 얻을 수 있는 최대 점수를 나타내는 정수 하나.