Problem D: Game (Medium-25)

Problem D: Game (Medium-25)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 627  Solved: 169
[Submit][Status][Web Board]

Description

Yuki is an ambitious girl and she is addicted to games.

In one game called The Queen's Gambit, Yuki is controlling the Queen to move in a grid of \(n\) rows and \(m\) columns, where rows are numbered from \(1\) to \(n\) and columns are numbered from \(1\) to \(m\). The cell at the \(i\)-th row and the \(j\)-th column is denoted by \((i,j)\). Each cell in the grid contains a point coefficient, denoted by \(C_{ij}\).

At first, Yuki can place the Queen on the grid arbitrarily, that is any cells in the grid can be the initial position for the Queen. Every turn Yuki can move the Queen between the cells sharing a common edge. For example, when the Queen is at \((i,j)\), it can be chosen to move to \((i-1,j)\), \((i+1,j)\), \((i,j-1)\) or \((i,j+1)\), if the destination is not out of the boundary.

Now every time when the Queen is moved from one cell to an unvisited cell, Yuki will gain the points which are equal to the product of two point coefficients. It means that Yuki will get \(C_{xy}\cdot C_{ij}\) points when the Queen moves from \((i,j)\) to \((x,y)\) and visits \((x,y)\) at the first time.

Yuki can stop the game at any time, and she wonders the maximum points she can gain.

Input

The first line contains two integers: \(n\), \(m\) \((1\leq n,m,p\leq 5\ 000,1\leq n\cdot m\leq50\ 000)\) — rows and columns of the grid.

Each of the next \(n\) lines contains \(m\) integers. The \(j\)-th number in the \(i\)-th line denotes \(C_{ij}\) \((C_{ij}\leq 5\ 000)\).

Output

Print one line with the result — the maximum points.

Sample Input

1 4
1 2 3 3

Sample Output

17

HINT

[Submit][Status]