说明

朱祁镇做皇上的时候，确切的来说是做太上皇的时候，有位叫也先的同志满怀希望的前来攻打京城，却落得这样一个 结果，弟弟被乱枪打死，几万军队被打的溃不成军，自己也被当初的手下败将打的到处乱跑，真是丢人啊。其实事情 到了这个地步，也该收手了，可是这位也先同志是一个很有个性的人，自他领军以来可谓横扫天下，在这里吃了如此 大亏，就这么走了吗，面子往哪里摆，于是他决定集合所有兵力转向攻击居庸关。我们将战场看作一个N * N （ 0 < N <= 1000）的棋盘，居庸关位于右下角。也先的计划是从左上角出发，每次进攻只能向右或者向下走，那么打到居庸关的时候他最多可以消灭多少守军（包括居庸关的守军）？

输入格式

第一行， 一个N（0 < N <= 1000)；

第二行到第N + 1行， 每行N个数字（都是正整数，且小于100000）， 表示此处的守军人数

输出格式

输出一个整数， 表示也先打到居庸关的时候最多可以消灭的守军人数（包括居庸关的守军）。

样例

4
1 2 3 4
5 6 9 8
9 1 0 1
2 3 4 5 

35