#1306. 2310. ParkII

2310. ParkII

#2310. ParkII

题目描述

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.   

注意:路径上有可能只有一个点. 

数据范围与提示