思路有点小奇怪，是接近 $O(n)$ 的，但是 WA 8 pts。

就是先在 $a_i$ 和 $b_i$ 中找出最小数。我们假设最小数是从 $a_i$ 中选出来的，那就把第 $i$ 行从左到右连起来，然后分别向上向下一行一行串通，串通的方法有两种（取代价最小的那一种）：

1. 把那一行从左到右串通起来，然后找一条最便宜的竖边把它和原来的一行连起来。

2. 原来一行的每个点都向新行的每个点连竖边。

如果最小值出在 $b_i$ 那就把行和列反过来处理即可。

代码也很简单易读，求各位 dalao 证伪或者 hack。

#include<bits/stdc++.h>
#define N 300005
#define int long long
using namespace std;

int n,m;
int a[N],suma,mina = 1e18,sa;
int b[N],sumb,minb = 1e18,sb;
int ans;

signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i = 1;i <= n;i++)
	{
		scanf("%lld",&a[i]);
		suma += a[i];
		if(a[i] < mina)
			mina = a[i],sa = i;
	}
	for(int i = 1;i <= m;i++)
	{
		scanf("%lld",&b[i]);
		sumb += b[i];
		if(b[i] < minb)
			minb = b[i],sb = i;
	}
	if(mina <= minb)
	{
		ans += (m-1)*mina;
		for(int i = sa-1;i >= 1;i--)ans += min(sumb,minb+(m-1)*a[i]);
		for(int i = sa+1;i <= n;i++)ans += min(sumb,minb+(m-1)*a[i]);
	}
	else
	{
		ans += (n-1)*minb;
		for(int i = sb-1;i >= 1;i--)ans += min(suma,mina+(n-1)*b[i]);
		for(int i = sb+1;i <= m;i++)ans += min(suma,mina+(n-1)*b[i]);
	}
	return printf("%lld\n",ans),0;
}