题目描述

给定三角形数塔，从顶层走到最底层，每次只能从第 i 行第 j 个数走到下一行的第 j 个数或第 j+1 个数，求路径上所有数之和的最大值。

输入格式

第一行 n。接下来 n 行，第 i 行包含 i 个整数。

输出格式

输出最大路径和。

样例

5
13
11 8
12 7 26
6 14 15 8
12 7 13 24 11

86

数据范围

1≤n≤1000，数塔中的每个数均为0至100的整数。