题目描述

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

输入格式

第一行 $m, n$。

接下来 $m$ 行每行 $n$ 个数即 $v_{i,j}$。

输出格式

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

2 3
1 -2 1
1 1 1

5

数据规模与约定

对于 $30\%$ 的数据，$n \leq 6$。
对于 $100\%$ 的数据，$m \leq 100$，$n \leq 8$。

提示

注意：路径上有可能只有一个点。