题目描述

给定一个共有 $n$ 层的数字三角形，第 $i$ 层恰好有 $i$ 个整数。

从顶部的数字出发，每次只能走到下一层中与当前位置相邻的两个数字之一。也就是说，如果当前在第 $i$ 层第 $j$ 个数字，那么下一步只能走到：

• 第 $i+1$ 层第 $j$ 个数字；
• 第 $i+1$ 层第 $j+1$ 个数字。

请你求出：从顶层到底层的一条路径中，路径上数字之和的最大值。

输入格式

第一行输入一个整数 $n$。
接下来 $n$ 行，第 $i$ 行输入 $i$ 个整数，表示数字三角形第 $i$ 层。
数据范围：

• $1 \le n \le 1000$
• $-10^4 \le a_{i,j} \le 10^4$

输出格式

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

4
5
7 8
2 3 4
4 9 6 1

25

Hint

样例解释： 一条最优路径为：

路径和为：