数塔

题目描述

有如下所示数塔，要求从顶层走到底层，若每一步只能走到下方相邻的结点，则经过的结点的数字之和最大是多少？ 

输入格式

第一行输入一个整数 $n$，表示数塔行数。 第二行到第 n+1 行表示数塔，第 $i$ 行有 $i-1$ 个整数 $k$ 用空格隔开。

输出格式

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

4
12
6 5
10 15 20
20 6 9 17

54

提示

####数据范围与提示 $1

来源

童程童美