数字矩阵

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

bLue 站在了一个 n*m 的填有数字的矩阵中,他可以选择从矩阵的四个顶点之一出发,到达斜对面的顶点。每一步必须向靠近目的地的方向移动,且每次移动都可以累加所在位置上的数字。

例如,bLue 选择从左上角出发,那么目的地为右下角,则他每次只能向右或向下移动一格。

现在他想知道在所有的走法中,能获得的最大累加和是多少。你能帮助他吗?

Input

输入数据有多组(数据组数不超过 50),到 EOF 结束。

对于每组数据:

  • 第 1 行输入 2 个整数 n, m (1 <= n, m <= 100),表示矩阵的行数和列数。
  • 接下来 n 行,每行包含 m 个用空格隔开的整数 aij (0 <= aij <= 10000),表示这个数字矩阵。

Output

对于每组数据,输出 1 行,包含 1 个整数,表示 bLue 能获得的最大的累加和。

Sample Input

3 4
1 2 3 4
1 0 6 5
4 7 2 0

Sample Output

28

Hint

Source

【2017年寒假集训分组测试赛2】bLue