题目描述

从数字三角形顶端出发，每步走到下一行的同列或下一列，求到底边的最大和。

输入格式

第一行 $n$，随后第 i 行有 i 个整数。

输出格式

输出最大路径和。

样例

4
2
3 4
6 5 7
4 1 8 3

21

数据规模与约定

$1\le n\le1000$，元素绝对值不超过 $10^6$。