题目描述

也许并不是很多人都知道，保加利亚即将启用第一家垃圾处理厂。其中的一项工作是压缩垃圾。为此，垃圾会被放入一个矩形“房间”中，房间的四面墙都是活塞，可以从对应的一侧推动垃圾。

另一方面，垃圾的成分并不均匀，不同位置需要不同的“压力”才能被压缩。

你可以把垃圾和房间看作一个 $N$ 行 $M$ 列的矩形矩阵。矩阵中每个格子里有一个 $0$ 到 $9$ 之间的整数 $A_{i,j}$，表示压缩该格子所需的“压力”。

当四面墙中的某一面推动当前剩余垃圾时，所需能量等于这一侧边界上的最大数字：

• 上墙或下墙，对应当前矩形的最上行或最下行；
• 左墙或右墙，对应当前矩形的最左列或最右列。

例如，若有一个 $3 \times 4$ 的压缩房间，垃圾的“硬度”为：

6 8 7 2
3 0 9 1
4 2 9 1

如果从上侧推动（即处理一行 6 8 7 2），所需力量为 $8$，因为这一行中最硬的格子是 $8$。类似地：

• 从下侧推动需要力量 $9$；
• 从左侧推动需要力量 $6$；
• 从右侧推动需要力量 $2$。

某一行或某一列一旦被推动，就会从当前矩形中消失，可以认为它已经被压缩，之后不再参与后续操作。目标是把全部垃圾（即所有格子）都压缩掉，并且总耗能尽可能小。

事实证明，活塞的选择以及使用顺序都会影响答案。比如：

• 若始终只用上侧活塞，则总耗能为 $8+9+9=26$；
• 若依次使用：上、右、右、左、下，则总耗能为 $8+1+9+4+2=24$。

听说了 Eli 那传奇般的创造力（尤其是把复杂问题交给你们来做这一点），垃圾处理厂的管理层任命她为“压缩部门负责人”。当然，她也给了你一个展示才华的机会：

请编写程序 garbage，求出压缩全部垃圾所需的最小能量。

输入格式

第一行输入两个正整数 $N,M$，表示房间的行数和列数。

接下来 $N$ 行，每行包含 $M$ 个一位整数，表示各个格子的垃圾硬度。

输出格式

输出一个整数，表示压缩全部垃圾所需的最小能量。

数据范围

• $1 \le N,M \le 100$
• $0 \le A_{i,j} \le 9$
• 在 50% 的测试点中，$1 \le N,M \le 10$

样例 1

输入

3 4
6 8 7 2
3 0 9 1
4 2 9 1

输出

24

样例 2

输入

8 7
9 5 9 9 8 9 1
1 3 7 0 1 7 7
6 0 7 3 7 0 3
2 2 6 1 5 4 8
6 9 9 2 3 2 7
4 6 7 3 1 1 3
1 6 7 1 2 6 7
4 4 7 3 9 8 9

输出

62