问题描述

一个城市的道路成了像棋盘那样的网状，东西向的路有 N 条，并从北向南从 1 标记到 N，南北向的路有 M 条，并由西向东从 1 标记到 M，每一个交叉点代表一个路口。

为了维护城市治安，需要在一些路口设置岗哨。在每一条东西向的路上，都必须设置且仅设置一个东西方向的岗哨，维护这条路的治安。同样地，在每一条南北向的路上，也必须设置且仅设置一个南北方向的岗哨，来维护这条路的治安。

一个路口最多只能设置一个岗哨。一个岗哨只能维护一条路的治安。在一个路口设置岗哨需要支付一定的费用。在不同的路口，设置岗哨的费用可能是不同的。

问：要想使每条路的治安都得到维护，最少需要支付多少费用？

输入

第一行：两个正整数 $N, M$

接下来一个 $N×M$ 的正整数矩阵 $C$：$C_{i,j}$ 表示在东西路 $i$ 与南北路 $j$ 的交叉路口处设置岗哨的费用。

输出

一个整数，表示需要支付的最少费用。

样例输入

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

样例输出

17

数据范围

30% 的数据：$2 ≤ N, M ≤ 20$

100% 的数据：$2 ≤ N, M ≤ 10^5， N×M <= 10^5， 1 ≤ C_{i,j} ≤ 10^9$