收割机2

题目描述

有一块土地，被划分成 n×m 的网格图（如图 1），在这块土地上以网格为单位种植了不同的农作物，每个网格里有一个整数 k，表示当前网格的总产量，现在有两台收割机分别为 A、B，A 收割机从网格的左上角出发，它只能向右和向下走，最终会走到右下角完成收割，B 收割机从网格的右上角出发，它只能向左和向下走，最终会走到左下角完成收割任务。在农作物没有被收割的情况下，两台收割机分别最多可以收割多少农作物。

网格图示例：

图1(n=3,m=4)

输入格式

第一行输入两个整数 n 和 m，表示网格图大小。

第二行到第 n+1 行，每行 m 个整数 k 用空格隔开。

输出格式

两个整数，分别表示 A、B 收割机可收割最多的产量。

样例输入 #1

3 4
1 2 1 1
3 3 2 2
2 1 6 1

样例输出 #1

16 14

数据范围

1≤n，m≤30，0≤k≤100

知识点与难度

本题涉及的知识点为动态规划基础，从属于 GESP 6级，难度等级：Mid-。

测试点分布