题目描述

《太空挖矿》

【太空挖矿】 星联盟在某太空区域发现可开采的矿石。现有一个n*m的星空图纸，图纸每个格子里标记了矿石的储量，图纸的左上角是入口，进入这片星域只能向右或者向下走，图纸的右下角是出口。 现在需要寻找一条可以开采矿石最多的路径，最终求这条路径可以开采多少矿石。

输入格式

第一行输入两个整数n和m，n表示图纸行数，m表示图纸的列数，整数之间使用空格隔开。(1 <= n,m <= 30) 第二行到第n+1行,每行m个数字,用空格隔开,每个数字表示一个区域内的矿石储量k。(0 <= k <= 3)

输出格式

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

样例

输入样例 1

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

输出样例 1

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