田小琳是一个游戏爱好者，最近她迷上了一款地牢探险类游戏。你是田小琳最好的朋友，她想邀请你与她一起通关这款游戏。 但是她只期待最终的boss之战，于是前面的关卡就落在了你的身上：在你面前的是一个边长为n（n<=500）的菱形地牢，这个地牢共有2n-1层，每层设有一定的房间，共有n^2个房间，每个房间都有相应的魔法值，房间的排列方式如图。
1 2 3 1 2 3 2 1 1
你只能由上到下的逐层探索，每层你必须选择一个房间并获取该房间的魔法值。由于地牢危险重重，所以你必须积累最多的魔法值才可以通关，聪明的你能计算出当前地牢能获得的最大的魔法值之和吗？
第一行包含一个整数n，表示边长为n的菱形地牢。
接下来有2n-1行数，每一行代表一层地牢。每一行的数分别代表这层地牢的房间内魔法值的大小。
输出包含一个数，代表可以获得的最大魔法值之和。