题目描述

一个数字三角形有 $n$ 行，第 $i$ 行有 $i$ 个数。从顶点开始，每步可以走到下一行同列或右邻列，直到最后一行。求经过数字之和的最大值。

输入格式

第一行一个整数 $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$ 之间。