K. Kid Rally
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

The primary school main event for every year is field trips, mainly consisting of a group of energized kids, organizing a special activity for this year.

The activity is to rally to the different places on a map size $$$N\times M$$$ in order to collect the score; each position is assigned a score $$$S_{i,j}$$$ for position $$$(i,j)$$$. The position can be considered as a point in $$$XY$$$ coordinate. All of the kids will be given a map and choose a partner to form a pair. Each person in the pair will start in position $$$(1,1)$$$ and $$$(1,M)$$$ before venturing on their own.

With consideration of limited time and the risk of injury, the school imposes four special rules for the activity.

1. If the kid stays at position $$$(x,y)$$$, this kid mustn't rally to position $$$(a,b)$$$ when $$$(a \leq x)$$$.

2. The path to rally from one position to another position must be a straight line.

3. The pairs' rally paths mustn't intersect at any point of the path regardless of the time that they reach each position.

4. The kid must stay in the area of the map and can choose to finish their rally at any place on the map.

The score of an individual person is the sum of the score on the persons' rally path. The final score for this activity is calculated by the multiplication of the pairs' scores. Alice and Bob want to form a pair and have the highest score in order to boast to their friends.

Your task is to assist Alice and Bob in reporting the maximum possible score that Alice and Bob can achieve.

Input

The first line contains two integers $$$N$$$ and $$$M$$$ $$$(2 \leq N,M \leq 1,000)$$$ — the rows and columns of the map respectively.

The $$$i^{th}$$$ line of the following $$$N$$$ lines describes the $$$i$$$-th row of the map in the format of $$$S_{i,1}$$$ $$$S_{i,2}$$$ $$$S_{i,3}$$$ ... $$$S_{i,M}$$$ $$$(0\leq S_{i,j} \leq 9)$$$ — the $$$i$$$-th row of the map consists of $$$M$$$ places with score $$$S_{i,j}$$$.

Output

The first line contains an integer $$$W$$$, the maximum possible score that Alice and Bob can achieve.

Example
Input
3 5
9 1 3 2 5
0 0 9 0 0
3 1 2 6 1
Output
240
Note

Alice's rally path is $$$(1,1) \rightarrow (3,1)$$$ which earns a score of 12.

Bob's rally path is $$$(1,5) \rightarrow (2,3) \rightarrow (3,4)$$$ which earns a score of 20.

Alice can't choose the rally path $$$(1,1) \rightarrow (3,4)$$$ and Bob can't choose the rally path $$$(1,5) \rightarrow (2,3) \rightarrow (3,1)$$$ because there is an intersection between the two rally paths.