测试数据来自 nnu_contest/1286

迷宫取数

时间限制:4s

空间限制:64MB

题目描述

$n*m$的二维迷宫中，每个位置上都有一个数。

选择一条从起点$(1,1)$到终点$(n,m)$的路径， 且在路径中，每个点至多经过一次。
将路径上的数字相加，可以得到一个和。求此和的最大值。

输入格式

第一行两个正整数$n,m$。

接下来$n$行，每行$m$个整数，表示这个迷宫。

输出格式

一个整数，表示和的最大值。

样例输入1

4 4
1     7     10    4
-99   -99   3    -99
-20   110  -10    4
4000  1    -9999  3

样例输出1

3990

样例1解释

1 + (-99) + (-20) + 4000 + 1 + 110 + (-10) + 4 + 3 = 3990

样例输入2

2 5
1900 5112 270 -6250 2850 
-3734 7803 425 8355 -46 

样例输出2

23549

样例2解释

1900+5112+7803+425+8355-46 = 23549

数据范围及限制

共$10$组测试数据，每个测试点$15$分。

对于前$40\%$的数据，$a_{ij} = 1$

对于$100\%$的数据，$1\le n,m\le 6, -10000\le a_{ij}\le 10000$。