题目描述

观测站记录了一座星塔的能量分布。第 $1$ 层有 $1$ 个能量值，第 $2$ 层有 $2$ 个能量值，依次类推，第 $h$ 层有 $h$ 个能量值。

你需要从塔顶出发，每次只能走到下一层中与当前位置相邻的两个位置之一，也就是正下方或右下方。路径经过的所有能量值会相加。

请你求出从塔顶走到塔底能够获得的最大能量和。

输入格式

第一行一个整数 $h$，表示星塔高度。

接下来 $h$ 行，第 $i$ 行有 $i$ 个正整数，表示第 $i$ 层的能量值。

输出格式

输出一行一个整数，表示最大能量和。

样例 #1

样例输入 #1

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

样例输出 #1

26

数据范围