题目描述

一次校园定向活动把补给点排成了三角形路线：第 $1$ 层有 $1$ 个点，第 $2$ 层有 $2$ 个点，依此类推，第 $r$ 层有 $r$ 个点。每个点都有一个积分。

同学从最上层的点出发，每次走到下一层中与当前位置相邻的两个点之一，直到到达最底层。请计算一条路线能获得的最大积分和。

输入格式

第一行一个正整数 $r$，表示层数。

接下来 $r$ 行，第 $i$ 行包含 $i$ 个整数，表示第 $i$ 层各点的积分。

输出格式

输出一行一个整数，表示从顶层走到底层能够获得的最大积分和。

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

30

样例说明

选择积分为 $7,3,8,7,5$ 的路线时，总和为 $30$，这是本样例中的最大值。

数据范围

对于 $100\%$ 的数据，$1\le r\le 1000$，所有输入整数均在 $[0,100]$ 范围内。