ParkII

时间限制:20s      空间限制:128MB

题目描述

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. 
注意:路径上有可能只有一个点. 

提示

没有写明提示


题目来源

没有写明来源