B20 实践-5 宝藏迷宫

题目描述

小 $Void$ 来到了一个装满宝藏的迷宫，迷宫由 $m\times n$ 的方格组成，每个格子里都有宝藏，用正整数 $val_{i,j}$ 表示宝藏的价值。

在迷宫中，小 $Void$ 每次只能走向他右边的格子或者下边的格子，所有小 $Void$ 走过格子里的宝藏他都会带走（包括起始点和终止点）。

他开始站在左上角的格子里，最终要从右下角的格子离开迷宫，请问他最多能拿走多少宝物？

下面就是一个 $2 \times 3$ 的迷宫：

小 $Void$ 开始在左上角，最优的线路是： 右、右、下，一路上得到的宝藏数依次为: $3,10,50,2$ 。

最终小 $Void$ 得到价值为 $65$ 的宝藏，为获得宝藏最多的走法。

输入格式

第一行两个整数 $m,n$，表示迷宫的行数和列数；

接下来的 $m$ 行每行 $n$ 个数 $val_{i,j}$ ，表示第 $i$ 行第 $j$ 列的格子中宝藏价值。

输出格式

一行一个整数，输出 小 $Void$ 可以拿到的宝藏最大值。

样例输入1

2 3
3 10 50
15 12 2

样例输出1

65

样例输入2

3 3
2 2 2
2 2 2
2 2 2

样例输出2

10

数据范围

对于 $100\%$ 的数据：$2\le m,n\le 100$，$1\le val_{i,j}\le 100$ 。