Description

After a tough journey, the protagonist Xiao P returns by airship. On the way back, he notices a long and narrow green patch standing out in the boundless desert. Looking closer, he realizes it is an amusement park designed for weary travelers.

The amusement park can be regarded as an area of size $n\times m$, and this $n\times m$ area is divided into $n\times m$ small grid cells, with one attraction in each cell.

However, Xiao P does not like all the attractions, so he assigns a satisfaction score to each one. A positive satisfaction means Xiao P likes this attraction, and the larger the value, the more he likes it. A negative value means he dislikes it, and the larger the absolute value, the more he dislikes it. A value of $0$ means he is neutral.

Xiao P decides to park the airship in some cell, and at each step he can move to one of the four adjacent cells: up, down, left, or right.

Xiao P wants to find a path that starts from the cell where the airship is parked and finally returns to that same cell.

Xiao P has a habit of not wasting time. Therefore, he wants every visited cell to be meaningful: whenever he reaches a place, he must experience the thrill there, whether or not he likes that attraction. Moreover, except for the cell where the airship is parked, he is unwilling to pass through any other cell twice. Xiao P wants to visit at least four cells.

Under these conditions, Xiao P hopes the sum of the satisfaction scores of the attractions he experiences is as large as possible. Can you help him find this maximum sum?

Input Format

The first line contains two positive integers $n$ and $m$, indicating the amusement park has size $n\times m$.

The next $n$ lines each contain $m$ integers. In the $(i + 1)$-th line, the $j$-th number represents the satisfaction score $a_{i,j}$ of the attraction in row $i$, column $j$ of the amusement park. Two integers in the same line are separated by a space.

Output Format

A single line containing one integer, the maximum possible sum of satisfaction scores.

4 4
100 300 -400 400
-100 1000 1000 1000
-100 -100 -100 -100
-100 -100 -100 1000

4000

Hint

Constraints

For $100\%$ of the data, it is guaranteed that $2\leq n\leq 100$, $2\leq m\leq 6$, $-10^3\leq a_{i,j}\leq 10^3$.

Translated by ChatGPT 5