题目描述

输入一个 $n$ 行 $m$ 列的数字矩阵 $a$：

$$\begin{bmatrix} a_{1,1} & a_{1,2} & \ldots & a_{1,m} \\ a_{2,1} & a_{2,2} & \ldots & a_{2,m} \\ \ldots & \ldots & \ldots & \ldots \\ a_{n,1} & a_{n,2} & \ldots & a_{n,m} \end{bmatrix}$$

我们用 $a_{i,j}$ 表示数字矩阵中第 $i$ 行第 $j$ 列的元素。

你可以对这个数字矩阵进行任意次如下操作：

任意选择矩阵中的一个元素 $a_{i,j}$ 并将其数值加 $1$ 或减 $1$。

进行一次上述操作的花费为 $1$。

你希望使用最小的花费，使得矩阵中每一行、每一列都是一个回文数列。

对于一个数列，如果这个数列和它倒序排列的数列相同，则我们称这个数列是一个 回文数列。比如：数列 $[1, 2, 3, 2, 1], [3,2,1,1,2,3]$ 都是回文数列。

你的任务是使每一行对应的数列，即：

• $a_{1, 1}, a_{1, 2}, a_{1, 3}, \ldots, a_{1, m}$
• $a_{2,1}, a_{2,2}, a_{2,3}, \ldots, a_{2,m}$
• ……
• $a_{n,1}, a_{n,2}, a_{n,3}, \ldots, a_{n,m}$

都是回文序列；同时，使每一列对应的数列，即：

• $a_{1, 1}, a_{2, 1}, a_{3,1}, \ldots, a_{n,1}$
• $a_{1,2}, a_{2,2}, a_{3,2}, \ldots, a_{n,2}$
• ……
• $a_{1,m}, a_{2,m}, a_{3,m}, \ldots, a_{n,m}$

也都是回文序列。

求：最小花费。

输入格式

第一行，两个整数 $n$ 和 $m$，表示数字矩阵的行数和列数（$1 \le n,m \le 1000$）。

接下来 $n$ 行，每行包含 $m$ 个整数，表示这个数字矩阵中的每个元素的数值。其中第 $i$ 行第 $j$ 列的元素表示 $a_{i,j}(0 \le a_{i,j} \le 10^9)$。

输出格式

输出一个整数，表示使该数字矩阵中每一行及每一列都是回文数列的最小总花费。

4 2
4 2
2 4
4 2
2 4

8

3 4
1 2 3 4
5 6 7 8
9 10 11 18

42

说明/提示

样例解释

样例1中，可以通过 $8$ 次操作得到如下满足条件的数字矩阵：

2 2
4 4
4 4
2 2

样例2中，可以通过 $42$ 次操作得到如下满足条件的数字矩阵：

5 6 6 5
6 6 6 6
5 6 6 5

数据规模与约定

• 对于 $30\%$ 的数据，$n,m \le 10, a_i \le 100$
• 对于 $60\%$ 的数据，$n,m \le 100, a_i \le 10^5$
• 对于 $100\%$ 的数据，$1 \le n,m \le 1000, a_i \le 10^9$