题目描述
马斯卡彭之王拥有自己的马斯卡彭王国，这里有数不清的马斯卡彭小蛋糕。马斯卡彭之王想要尽快回到自己的王宫（第一层），他从最底层出发，每次向上一层他就会吃掉那个位置的马斯卡彭蛋糕，并且他每次只会向上层走。马斯卡彭小蛋糕太好吃了！因此马斯卡彭之王想要在回到王宫的路上吃到最多的马斯卡彭蛋糕，将每个位置的马斯卡彭蛋糕数量用数字替换后马斯卡彭大王的回宫之路示例如下图。
在上面的样例中，从5→7→8→3→7的路径能吃到最多的马斯卡彭蛋糕。
在上面的样例中，从5→7→8→3→7的路径能吃到最多的马斯卡彭蛋糕。
输入
第一个行一个正整数n（ 1 <= n <= 103 ),表示马斯卡彭大王回宫需要经过的层数。
下面n行每行为第n-1层的马斯卡彭蛋糕数量,所有整数均在[0,100]范围内。
下面n行每行为第n-1层的马斯卡彭蛋糕数量,所有整数均在[0,100]范围内。
输出
单独的一行,输出马斯卡彭之王最多吃到的马斯卡彭蛋糕数量。
样例输入
Copy
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出 Copy
30
来源/分类