题目描述

现在你面对一个n×m的矩阵，矩阵中的每一个元素都是一个整数，现在你需要计算从矩阵的左上角走到右下角所走过的所有元素相加的最大和。
注意：只能向右或者向下走，不能走出边界。

输入描述

输入第一行包含两个用空格分开的整数n (1≤ n ≤ 100)和m (1≤ m ≤ 100)，表示n行m列的矩阵；接下来是n行每行包含m个用空格分开的非负的整数A (0 ≤ A ≤ 100)。

输出描述

输出从矩阵的左上角走到右下角所走过的所有元素相加的最大和。

示例

提示

Sample test中最大和为1+2+3+2=8。
更多样例：

input

5 3
14 14 4
76 5 76
78 23 23
45 75 53
52 43 71

output

412

最大和为14+76+78+45+75+53+71=412

相关标签