1109: 奖励关

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:47 Solved:10

Description

小航参加了某闯关游戏,历尽艰辛来到最后一个奖励关,规则如下:

①玩家最初站在一个 n 行 m 列矩阵的左上角的格子里,矩阵的每一个格子中都有一个数字

②玩家每到一个格子可以获得当前格子对应数字的奖金

④玩家每次只可以向右或向下移动一格,走到右下角的格子里则游戏结束

求小航最多可以得到多少奖金?

Input

第一行2个正整数n和m,表示一个n行m列的矩阵

接下来n行,每行输入m个数字,表示这个矩阵上的数字

Output

一个整数,小航最多可以得到的奖金数

Sample Input Copy

3 4
1 2 6 3
3 5 1 2
4 1 3 1

Sample Output Copy

15

HINT

样例解释

1+2=3

3+6=9

9+3=12

12+2=14

14+1=15

可以证明找不到比15大的走法,故输出15

数据范围

所有输入数据均大于0且小于100