Gem Collection Optimization

Before Artoria Pendragon becomes a heroic spirit, she must pull the sword from the stone to become King Arthur. Before doing so, she needs to collect some precious gems.

The gems are arranged on an \(n \times m\) grid. Each cell \((i, j)\) contains a gem worth \(v_{i,j}\). Artoria may choose her starting cell arbitrarily. Time starts at \(0\) seconds. Every second, the following operations occur in order:

1. At the beginning of the \(i\)th second, if Artoria is at cell \((x, y)\), she may pick up the gem in that cell (if it has not been taken before).
2. If \(i\) is an even number, immediately after (1) the gems in the four cells adjacent (up, down, left, right) to \((x, y)\) vanish from the grid.
3. If at the start of the \(i\)th second Artoria is at cell \((x, y)\), then at the beginning of the \((i+1)\)th second she can move instantaneously to any one of \((x+1, y)\), \((x-1, y)\), \((x, y+1)\), or \((x, y-1)\), or she may choose to remain at \((x, y)\).

Your task is to determine the maximum total value of gems that Artoria can collect.

Note: Observe that the vanish event in every even second eliminates the gems in the cells adjacent to the cell where Artoria is located at that moment. With the movement restrictions, it turns out that no matter what route she takes, only one gem—the one in her starting cell—will ever be available for collection. Therefore, the answer is simply the maximum gem value among all cells in the grid.

inputFormat

The first line contains two positive integers \(n\) and \(m\) (\(1 \leq n, m \leq 100\)), representing the number of rows and columns of the grid, respectively.

Each of the following \(n\) lines contains \(m\) integers \(v_{i,j}\) (\(1 \leq v_{i,j} \leq 10^9\)), where \(v_{i,j}\) is the value of the gem in the cell of the \(i\)th row and \(j\)th column.

outputFormat

Output a single integer representing the maximum total gem value Artoria can obtain.

sample

1 1
5

5