题目描述

给出一个 $n$ 行的数字三角形，第 $i$ 行有 $i$ 个数。从第一行的数出发，每次可以走到下一行中与当前数左右相邻的两个数之一，一直走到第 $n$ 行。求一路上经过的数字之和的最大值。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行有 $i$ 个整数，相邻两数之间用一个空格隔开。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

30

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 500$，每个数在 $0\sim 1000$ 之间。