题目描述

从数字三角形的顶端出发，每次从 $(i,j)$ 走到 $(i+1,j)$ 或 $(i+1,j+1)$，走到底行。求路径上数字之和的最大值。

输入格式

第一行行数 $n$，随后 $n$ 行，第 $i$ 行有 $i$ 个整数，表示数字三角形。

输出格式

输出最大总和。

样例

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

30

数据范围

$1\le n\le100$，每个数是0至99的整数。