Description

This is before Artoria Pendragon became a Heroic Spirit. She is about to pull the sword from the stone to become King Arthur, and before that she needs to collect some gems.

The gems are arranged in an $n \times m$ grid. Each cell contains a gem worth $v_{i,j}$. Artoria Pendragon may choose her own starting cell.

The initial time is $0$ seconds. The following operations are executed every second, in order.

1. At the beginning of second $i$, if Artoria Pendragon is on cell $(x, y)$, she can take the gem in $(x, y)$.
2. At even-numbered seconds, the gems in the four orthogonally adjacent cells around Artoria Pendragon disappear.
3. If Artoria Pendragon is on cell $(x, y)$ at the beginning of second $i$, then at second $i+1$ she may immediately move to $(x+1, y)$, $(x, y+1)$, $(x-1, y)$, or $(x, y-1)$, or stay at $(x, y)$.

Find the maximum total value of gems that Artoria Pendragon can obtain.

Input Format

The first line gives the numbers $N, M$, representing the number of rows and columns. $N, M \le 100$. The value of each gem does not exceed $10000$. The next $N$ lines and $M$ columns describe the value matrix.

Output Format

Output the maximum total value of gems that can be taken.

2 2
1 2
2 1

4

Hint

An original problem by Yao Jinyu.

Translated by ChatGPT 5