题目描述

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

输入格式

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

输出格式

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

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

10

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,m \le 10^3$ ， $0 \le k \le 10^3$。