题目描述

给定一个 $n$ 行 $m$ 列的矩阵 $A$，其中第 $i$ 行第 $j$ 列的元素记为 $a_{i,j}$。

您正在用这个矩阵玩一个游戏，您的目标是最大化总得分。

您的每一个回合可以选择如下两个操作之一进行：

操作一：选择相邻的两行（令其为 $i,i+1$ 行），获得这两行的所有元素之和的分数，然后将这两行通过向量的加法合并。 $$ \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} $$

操作二：选择相邻的两列（令其为 $j,j+1$ 列），获得这两列的所有元素之和的分数，然后将这两列通过向量的加法合并。

$$ \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} $$

当无法进行操作的时候，游戏结束，试求总得分的最大值。

输入格式

第一行两个正整数 $n,m$。

接下来 $n$ 行，每行包含一个长度为 $m$ 的，仅由数字 $1 \sim 9$ 组成的字符串。其中第 $i$ 个字符串的第 $j$ 个字符表示 $a_{i,j}$。

输出格式

输出一行一个整数表示得分的最大值。

样例

样例输入 #1

3 3
314
159
265

样例输出 #1

130

样例解释 #1

进行 $4$ 次操作：

• 合并第 $2,3$ 列，得分 $1+5+6+4+9+5=30$
• 合并第 $2,3$ 行，得分 $1+14+2+11=28$
• 合并第 $1,2$ 行，得分 $3+5+3+25=36$
• 合并第 $1,2$ 列，得分 $6+30=36$

总分 $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} $$

样例输入 #2

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

样例输出 #2

4555

数据范围与约定

对于所有数据，有：

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

子任务：