Problem D: Points

Problem D: Points

Time Limit: 2 Sec  Memory Limit: 128 MB
Submit: 706  Solved: 170
[Submit][Status][Web Board]

Description

Yuki is an ambitious girl and she is addicted to a game called Honor of Kings.

In the game, Yuki is controlling the King 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 King on the grid arbitrarily, that is any cells in the grid can be the initial position for the King. Every turn Yuki can move the King between the cells sharing a common edge. For example, when the King 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 King is moved from one cell to an unvisited cell, Yuki will gain the points which is equal to the product of two point coefficients. It means that Yuki will get \(C_{xy}\cdot C_{ij}\) points when the King 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 score she can gain.

Input

The first line contains two integers: \(n\) and \(m\) \((1\leq n,m\leq 50\ 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}\) \((1\leq 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]