题目描述

晶晶最近迷上了数字迷宫游戏，整天沉浸在一串串看似简单的数字中自得其乐。数字迷宫游戏的魅力体现在变化中隐含着不变的规律，归纳是探究数字迷宫的法宝之一。

下图就是一个由线连接起来的数字小方格组成的数字迷塔。

一个迷塔共 $n$ 层，它由 $n×(n+1)/2$ 个小方格组成。每个小方格中都有一个数字，并且连着下一层的两个小方格。现从塔顶走到塔底，每一步只能走到相邻的方格中，则经过方格的数字之和最大值是多少？这个问题晶晶已经琢磨一天了，她感觉异常棘手。你能帮帮她吗？

输入格式

输入数据共 $n+1$ 行，第 $1$ 行是一个整数 $n(1 \le n \le 1000)$，表示数字迷塔的高度，接下来用 $n$ 行数字表示数字迷塔，其中第 $i$ 行有 $i$ 个正整数，且所有的正整数均不大于 $100$。

输出格式

输出可能得到的最大和。

样例

5
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16

59

样例解释

$9->12->10->18->10$ ，按照这条路径，实现数字和最大值 $59$。