题目描述

这是一场规模不小的点兵。

你手下有 $n\times m$ 名士兵，现在他们站成了一个 $n$ 行 $m$ 列的矩阵。为了提高军队的凝聚力，你要选出一些小队长来帮助你管理这些士兵。

选择每一名士兵当小队长的代价不同，可以用一个数值 $a_{i,j}$ 来描述选择第 $i$ 行第 $j$ 列的士兵成为小队长所需要的代价，也就是花费 $a_{i,j}$ 的代价就可以使得第 $i$ 行第 $j$ 列的士兵管辖第 $i$ 行 或 第 $j$ 列。

你想知道使得每行每列都被管辖所需要的最小总代价。请注意，你不能花费两倍代价使一名士兵同时管辖他所在的行和列。

输入格式

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

接下来 $n$ 行，每行 $m$ 个整数表示一个 $n\times m$ 的矩阵 $a$。

输出格式

一行一个整数表示答案。

4 4
5 8 2 10
3 7 6 9
1 4 11 14
16 2 5 7

29

数据范围

• 对于 $30\%$ 的数据，$2\leq n\leq m\leq 5$；
• 对于 $70\%$ 的数据，$2\leq n\leq m\leq 50$；
• 对于 $100\%$ 的数据，$2\leq n\leq m\leq 10^5$，$n\times m\leq 10^5$，$1\leq a_{i,j}\leq 10^9$。