5271 - 路径和最大

题目描述

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

输入

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

输出

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

样例

输入

3 3 
1 1 0 
0 1 1 
0 1 1 

输出

5

输入

2 2 
0 1 
1 0 

输出

1
说明

对于所有数据点,保证(1 ≤ n ≤ 100),(1 ≤ m ≤ 100) 。

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 29
通过人数 3
金币数量 2 枚
难度 未标记


上一题 下一题