路径和最大

题目描述

给定一个 n 行 m 列的二维数组，数组中的元素都是 0 或 1。从数组的左上角 (0, 0) 出发，每次只能向右或向下移动一格，要求找出一条从左上角到右下角 (n - 1, m - 1) 的路径，使得路径上经过的 1 的数量最多。输出这个最大的 1 的数量。

输入

第一行输入两个正整数 n 和 m，分别表示二维数组的行数和列数。
接下来 n 行，每行输入 m 个 0 或 1，用空格分隔。

输出

输出一个整数，表示路径上经过的 1 的最大数量。

样例

输入 1

3 3 
1 1 0 
0 1 1 
0 1 1

输出 1

5

输入 2

2 2 
0 1 
1 0 

输出 2

1