题目描述

数字三角形的走法同上：从顶端出发，每步走到正下方或右下方，直到底行。额外要求路径经过第 $\lfloor n/2\rfloor$ 行第 $\lfloor n/2\rfloor$ 个数。求路径数字和最大值。

输入格式

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

输出格式

输出最大总和。

样例

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

28

数据范围

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