题目情景

希蒙最近在学习动态规划，其中有一个问题就是数塔问题，不过希蒙又觉得，单纯的数塔问题太简单了，因此希蒙决定来玩玩新花样。现在的数塔是由两个相对的三角形组成

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

保证总行数为奇数

现在希蒙想知道，现在它位于两个三角形的顶尖，也就是正中间这个位置，它可以选择向上移动或者向下移动，但是一旦选择之后，就不能更改方向了。在移动中，希蒙每次可以移动一层的位置，移动后可以保留当前位置不动，也可以选择向左移动一格或者向右移动一格，问：希蒙如何选择，才能在走到第一行或者最后一行的时候，取得最大的数字和。

输入格式

第一行：输入一个正整数n，数塔的行数

接下来的n行，对应数塔每一行的数字

输出格式

共一行n个数字：经过题目中的排序后，每个机器人头部的编号

样例

输入样例1

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

输出样例1

21

输入样例2

3
-5 -4 -1
-6
-2 -3 -8

输出样例2

-7

数据范围与提示

对于100%的数据：n<=500，且数塔中的数字绝对值小于等于$10^6$