Given an $n \times m$ matrix $A$, where the element at the $i$-th row and $j$-th column is denoted by $a_{i,j}$.

You are playing a game with this matrix, and your goal is to maximize the total score.

In each turn, you can perform one of the following two operations:

Operation 1: Choose two adjacent rows (let them be row $i$ and $i+1$), gain a score equal to the sum of all elements in these two rows, and then merge these two rows by vector addition. $$ \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,m} \end{pmatrix} \to \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{i-1,1} & a_{i-1,2} & \cdots & a_{i-1,m} \\ a_{i,1} + a_{i+1,1} & a_{i,2} + a_{i+1,2} & \cdots & a_{i,m} + a_{i+1,m} \\ a_{i+2,1} & a_{i+2,2} & \cdots & a_{i+2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,m} \end{pmatrix} $$

Operation 2: Choose two adjacent columns (let them be column $j$ and $j+1$), gain a score equal to the sum of all elements in these two columns, and then merge these two columns by vector addition. $$ \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,m} \end{pmatrix} \to \begin{pmatrix} a_{1,1} & \cdots & a_{1,j-1} & a_{1,j} + a_{1,j+1} & a_{1,j+2} & \cdots & a_{1,m} \\ a_{2,1} & \cdots & a_{2,j-1} & a_{2,j} + a_{2,j+1} & a_{2,j+2} & \cdots & a_{2,m} \\ \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,j-1} & a_{n,j} + a_{n,j+1} & a_{n,j+2} & \cdots & a_{n,m} \end{pmatrix} $$

The game ends when no more operations can be performed. Find the maximum total score.

Input

The first line contains two positive integers $n$ and $m$.

The next $n$ lines each contain a string of length $m$ consisting only of digits $1 \sim 9$. The $j$-th character of the $i$-th string represents $a_{i,j}$.

Output

Output a single integer representing the maximum total score.

Examples

Input 1

3 3
314
159
265

Output 1

130

Note 1

Perform 4 operations:

• Merge columns 2 and 3, score $1+5+6+4+9+5=30$.
• Merge rows 2 and 3, score $1+14+2+11=28$.
• Merge rows 1 and 2, score $3+5+3+25=36$.
• Merge columns 1 and 2, score $6+30=36$.

Total score $30+28+36+36=130$. $$ \begin{pmatrix} 3 & 1 & 4 \\ 1 & 5 & 9 \\ 2 & 6 & 5 \end{pmatrix} \rightarrow \begin{pmatrix} 3 & 5 \\ 1 & 14 \\ 2 & 11 \end{pmatrix} \rightarrow \begin{pmatrix} 3 & 5 \\ 3 & 25 \end{pmatrix} \rightarrow \begin{pmatrix} 6 & 30 \end{pmatrix} \rightarrow \begin{pmatrix} 36 \end{pmatrix} $$

Input 2

10 8
82974679
74744362
34499984
86891758
56419363
76176864
78392791
71539599
44588446
71227999

Output 2

4555

Constraints

For all data:

• $1 \le n,m \le 3 \times 10^3$
• $1 \le a_{i,j} \le 9$

Subtasks