题目描述

在n*n的数字矩阵中，从左下角开始，每次只能向上或向右进入相邻的方格，不能走到方格外，一直走到右上角，问路径上的数字和最大是多少？

输入格式

第一行一个数n，范围[1,100]；

第2到n+1行，每行n个整数，范围[-1000,1000]；

输出格式

一个整数，最大和。

输入/输出例子1

5
1  2  3   4   5
-4  5  6  -8   9
5  3 -8  12 -20
1  0  2  -5   3
4  1  2   3  7

36

解释：和最大的路径序列是4 1 5 3 5 6 3 4 5