当前没有测试数据。

题目描述

给定一个 $n$ 层的数字金字塔，第 $i$ 层有 $i$ 个数字。从顶部出发，每次可以移动到下一层相邻的两个数字上。请计算从顶部到底部的路径上数字之和的最大值。

输入格式

第一行输入一个整数 $n$，表示金字塔的层数。

接下来 $n$ 行，第 $i$ 行输入 $i$ 个整数，表示第 $i$ 层的数字。

输出格式

输出一个整数，表示路径上数字之和的最大值。

样例 #1

输入

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

输出

30

样例说明

样例 1 解释

最优路径：$7 \to 8 \to 1 \to 7 \to 5$，和为 $30$。

数据范围

对于 $100\%$ 的数据，$1 \le n \le 500$，每个数字的绝对值不超过 $1000$。