题目描述

小明被困在一个n*n的迷宫里面，小明需要从迷宫的左上角出发，走到迷宫的右下方，每个迷宫房间里面都有一定数量的金币，走过一次的迷宫回坍塌，无法返回；且小明每次只能往右，或者往下的迷宫房间走。求小明发走出迷宫后，最多能拿到多少金币。

输入格式xi

一个数 $n$。代表n*n的迷宫，有n * n个房间。

接下来n行，每行n个数字xi，代表每个房间的金币数量。

输出格式

最多能捡到的金币数量

4
63 39 11 31
94 85 72 32
54 27 95 68
35 92 5 88

565

数据规模与约定

对于 $100\%$ 的数据，$0 \le n \le 10^3$，$1 \le xi \le 100$。