Maximize Amusement Park Satisfaction

After an arduous journey, our protagonist Xiao P returns by airship and discovers a peculiar amusement park in the middle of a vast desert. The park is arranged as an \(n \times m\) grid, where each cell represents an amusement project with a given satisfaction rating. A positive rating indicates that Xiao P likes the project, a negative rating means he dislikes it, and a rating of zero shows indifference.

Xiao P parks his airship at any cell and then moves in the four cardinal directions (up, down, left, right). He plans a cycle path that starts and ends at the airship cell under the following conditions:

• Every cell entered must be experienced; that is, once he arrives at a cell he must try the amusement project there. Except for the airship (starting) cell, no cell may be visited more than once.
• The cycle must include at least four cells.

The goal is to maximize the sum of the satisfaction ratings of the projects visited in the cycle. Formally, let the park be an \(n \times m\) grid where each cell \((i,j)\) has satisfaction rating \(a_{i,j}\). Find a cycle that starts and ends at the same cell, visits at least four cells (with the starting cell only counted once), and maximizes \(\sum a_{i,j}\) over the visited cells. If no valid cycle exists, output -1.

inputFormat

The first line contains two integers \(n\) and \(m\) (with \(1 \le n, m \le 6\)), representing the number of rows and columns of the park, respectively.

The next \(n\) lines each contain \(m\) integers, where the \(j\)-th integer in the \(i\)-th line is the satisfaction rating \(a_{i,j}\) for that project.

outputFormat

Output a single integer representing the maximum total satisfaction rating that can be achieved by a valid cycle. If no valid cycle exists, output -1.

sample

3 3
1 2 3
4 -5 6
7 8 9

40