终于...经过你的不懈努力，你和田小琳一起来到了boss之战，但在田小琳与boss决斗之前，你还得想出一个高阶地牢的魔法值收集方案。这个高阶地牢收集魔法值的规则只是在前面的关卡规则上多了一个条件：每次选下一层的房间时，只能从与你当前所选房间相邻的（下一层的）两个房间里选择。 为了最终决斗，你依然要积攒最多的魔法值。你能算出高阶地牢能获得的最大魔法值之和吗？
输入描述:
第一行包含一个整数n（n<=500），表示边长为n的菱形地牢。
接下来有2n-1行数，每一行代表一层地牢。每一行的数分别代表这层地牢的房间内魔法值的大小。(每个房间的魔法值都小于5000)
输出描述:
输出包含一个数，代表可以获得的最大魔法值之和。