测试数据来自 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\)。