信息接力

哨兵调度完了，但信息需要接力——从一端传到另一端。

"接力？"CC问。

"对。"你说，"一个$n\times m$的网格，从左上角走到右下角。每次可以向右或向下走。求路径上数字之和的最大值。"

"最大？"

"对。"你说，"不是所有路径都一样，要选数字大的走。"

"咋走？"

"动态规划。"你说，"$dp[i][j]$表示到$(i,j)$的最大和。"

"转移？"

"从上面或左面来。"你说，"$dp[i][j]=a[i][j]+\max(dp[i-1][j],dp[i][j-1])$。"

"第47格。"你说，"$(4,7)$——如果值是47，从上面或左面选大的来。"

"上面的值？"

"看$dp[3][7]$。"你说，"如果它比$dp[4][6]$大，就从上面来。"

"路线？"

"对。"你说，"最后从$dp[n][m]$倒推，就能知道路线。"

"像迷宫？"

"对。"你说，"像迷宫——但每条路有分数，选总分最高的。"

"如果分数一样？"

"随便选。"你说，"一样的话，哪条都行。"

"能到吗？"

"能。"你说，"只要网格连通，总能到。"

CC看着网格——像一张网，像一张地图，像某种必须一步一步走的路。

"一步一步。"她说，"不能跳。"

"对。"你说，"只能向右或向下。"

"像人生。"她说，"只能往前。"

"对。"你说，"但可以选择哪条路。"

Echo把最优路径标出来——一条亮线，在网格中蜿蜒。

"以前我乱走。"她说，"现在……有方向了。"

"因为你在算。"你说。

"对。"她说，"因为我在算。"

题目描述

$n\times m$网格，每个格子有数字。从$(1,1)$走到$(n,m)$，只能向右或向下。求路径上数字之和的最大值。

输入格式

第一行$n$和$m$。接下来$n$行，每行$m$个整数。

输出格式

最大路径和。

输入样例

5
1 2 3 4 5

输出样例

12

提示

• $dp[i][j]=a[i][j]+\max(dp[i-1][j],dp[i][j-1])$。
• 边界：$dp[1][1]=a[1][1]$。
• 时间复杂度$O(nm)$。