题目描述

您身处在一个n*n的正方形迷宫中，你在第一行第一列的位置出发，每个格子的迷宫都有相应数量的宝藏金币g，每次只能选择下方或者右方的格子前进，假设你有哆啦A梦的百宝袋，可以装走所有的金币，其中只有（n,n）格子是出口。 问这次寻宝之旅你最多能获得多少金币？

输入格式

第一行一个正整数 $n$，代表n*n的迷宫。 接下来n行n列，代表每个迷宫格子的金币数量。

输出格式

输出一个整数，代表从（n,n）出口获得的最多金币数量。

5
5 1 1 1 6 
9 8 5 7 1 
6 8 2 8 8 
1 5 4 4 4 
4 9 2 9 5 

60

数据规模与约定

对于 $100\%$ 的数据，$5 \le n \le 30$。 金币$1 \le g \le 9$