数字金字塔

题目描述

小登山家在爬一座数字金字塔：金字塔共 $n$ 层，第 $i$ 层有 $i$ 个数。从塔顶出发，每步可以走到左下方或右下方一格，直到塔底。

走过的数字之和最大是多少？

输入格式

第一行，一个整数 $n$。

接下来 $n$ 行，第 $i$ 行有 $i$ 个整数，用空格分隔。

输出格式

一行，一个整数，表示最大路径和。

数据范围