T497034 如何优雅地卡 Spfa

>众所周知，根据 Spfa 的 bfs 特性，在非负权图上可以考虑构造如下图所示的，存在多个次短路的网格状结构，从而把 spfa 卡到 $O(n^2)$ 级别。 > >如下图所示，对于某一个节点存在多条从起点到它的路径。由于竖边的权值为 0，包含横边和斜边数相同的路径长度相近。但由于包含边数不同，这些路径被遍历的顺序也不同。这就可能造成该节点的重复入队，从而导致后继节点被重复更新的情况。 > > > >——「笔记」如何优雅地卡 Spfa - Luckyblock，https://www.cnblogs.com/luckyblock/p/14317096.html（**请勿在赛时打开！！！而且和这题没有任何关系看了也没用！！！**） 阅读了上述企图卡掉 spfa 的丧心病狂博客后，您感觉无比的胆战心慌肉颤心惊跼蹐不安胆丧魂惊。一蛇吓十年，三年怕草绳，您决定这辈子再也不在网格图上跑最短路了——然而您现在遇到了一个需要在网格图上跑最小生成树的问题：

给定一个 $n\times m$ 的网格图，行从 $1\sim n$ 编号，列从 $1\sim m$ 编号，网格图中点可用它所在的行编号 $r$ 与所在的列编号 $c$ 表示为 $(r, c)$。 点 $(i,j)$ 与 $(i,j+1)$ 间连有一条权值为 $a_i$ 的边，其中 $1\le i\le n, 1\le j

第一行有两个正整数 $n, m(3\le n, m \le 3\times 10^5)$，代表网格图的行数与列数。 第二行有 $n$ 个正整数 $a_i(1\le i\le n, 1\le a_i\le 10^5)$，含义如题目描述所示。 第三行有 $m$ 个正整数 $b_j(1\le j\le m, 1\le b_j\le 10^5)$，含义如题目描述所示。

一行一个整数表示答案。

样例说明：最小生成树中的边包括第一行上的所有边，第一列、第二列、第三列上的所有边。