"Watch your six!"

最近Chair在玩使命召唤，但是因为菜得特别，所以特别地菜，在敌人的包围圈中，倒霉的Chair表示每次回头都会看到一万个敌人！然后壮烈牺牲，那么问题就来了——现在Chair打开了修改器，要把这群可恶的敌人干掉，那么在包围圈中Chair应当如何突围？

请保证Chair消灭最多敌人并且冲出包围圈。假设Chair在左上角，达到右下角时算突围成功。

4

1 2 3 4

5 6 9 8

9 1 0 1

2 3 4 5

值得注意的是，Chair是如此英勇，应当一往无前，也就是说只能向下或向右走。

图示应为最大战果——于是你应该输出他们的和：35



输入
第一行，一个N

第二行至N+1行，每行N个数字，表示这点的敌人人数

输出
消灭敌人的总和

输入范例
4

1 2 3 4

5 6 9 8

9 1 0 1

2 3 4 5
输出范例
35