太空挖矿

题目描述

星联盟在某太空区域发现可开采的矿石。现有一个 $n \times m$ 的星空图纸，图纸每个格子里标记了矿石的储量，图纸的左上角是入口，进入这片星域只能向右或者向下走，图纸的右下角是出口。

现在需要寻找一条可以开采矿石最多的路径，最终求这条路径可以开采多少矿石。

输入格式

第一行输入两个整数 $n$ 和 $m$（$1 \le n, m \le 30$），整数之间使用空格隔开。

第二行到第 $n+1$ 行，每行 $m$ 个数字，用空格隔开，每个数字表示一个区域内的矿石储量 $k$（$0 \le k \le 3$）。

输出格式

一个整数，表示可以开采的最大矿石数。

样例输入 1

3 4
1 2 2 3
2 1 1 0
2 0 3 1

样例输出 1

10

样例解释 1

一条最优路径是 $(1,1) \to (1,2) \to (1,3) \to (2,3) \to (3,3) \to (3,4)$，经过格子里的储量依次是 $1, 2, 2, 1, 3, 1$，总和为 $1+2+2+1+3+1=10$，所以答案是 10。

样例输入 2

1 5
1 0 2 3 1

样例输出 2

7

样例输入 3

5 1
1
2
0
3
1

样例输出 3

7

样例输入 4

4 4
1 0 2 2
2 0 2 2
2 0 0 2
2 2 2 1

样例输出 4

12

数据范围

• $1 \le n, m \le 30$
• $0 \le k \le 3$