#2310. ParkII

内存限制:128 MiB 时间限制:20 Sec

题目描述

Hnoi2007-Day1有一道题目 Park:给你一个 m * n 的矩阵,每个矩阵内有个
权值V(i,j) (可能为负数),要求找一条回路,使得每个点最多经过一次,并且经过
的点权值之和最大,想必大家印象深刻吧.
无聊的小 C 同学把这个问题稍微改了一下:要求找一条路径,使得每个点
最多经过一次,并且点权值之和最大,如果你跟小 C 一样无聊,就麻烦做一下
这个题目吧.

输入格式

第一行 m, n,接下来 m行每行 n 个数即. 
V( i,j)

输出格式

一个整数表示路径的最大权值之和.

样例

样例输入


			
2 3
1 -2 1
1 1 1

样例输出


			
5
【数据范围】
30%的数据,n≤6.
100%的数据,m<=100,n ≤ ≤8.
注意:路径上有可能只有一个点.

数据范围与提示