首先我们需要行列建模，把 $n$ 个点放在左边，$m$ 个点放在右边，左边向右边两两连边，边权就是原网格图的对应点权。方向表示它管理横的还是竖的。然后每个点最多只能有一条入边（因为只能被一个掌管）。所以就变成了求 $n+m$ 个点的最小生成基环树森林。

具体地，我们在并查集中额外维护一个size表示连通块中环的个数。先按照边权排序，然后如果只要总共的环个数不超过 $1$ 就能连，同一个连通块内如果没连成过环也可以连。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0;
	char e=getchar();
	while(e<'0'||e>'9') {
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x;
}
const int N=100005;
int n,m;
int fa[N<<1];
bool siz[N<<1];
int Find(int x) {
	if(x==fa[x])return x;
	return fa[x]=Find(fa[x]);
}
struct node {
	int x,y,z;
} a[N];
int tot;
bool cmp(node A,node B){
	return A.z<B.z;
}
signed main() {
//	freopen("ex.in","r",stdin);
//	freopen(".out","w",stdout);
	R(n),R(m);
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j) {
			int R(c);
			a[++tot]= {i,j+n,c};
		}
	}
	sort(a+1,a+1+tot,cmp);
	int ans=0;
	for(int i=1;i<=n+m;++i){
		fa[i]=i;
	}
	for(int i=1; i<=tot; ++i) {
		int x=a[i].x,y=a[i].y,z=a[i].z;
		int fx=Find(x),fy=Find(y);
		if(fx!=fy) {
			if(siz[fx]+siz[fy]<=1) {
				ans+=z;
				siz[fx]+=siz[fy];
				fa[fy]=fx;
			}
		} else if(siz[fx]+siz[fy]==0) {
			siz[fx]=1;
			ans+=z;
		}
	}
	cout<<ans<<"\n";
	return 0;
}