Strange Graph

You are given a two-dimensional array of integers of size $N \times K$, $A$ $=$ $A\_{0,0}$, $A\_{0,1}$, $\dots$, $A\_{0,K-1}$, $A\_{1,0}$, $\dots$, $A\_{N-1,K-1}$ and also arrays of integers of size $M$, $U$ $=$ $U\_{0}$, $\dots$, $U\_{M-1}$ and $V$ $=$ $V\_0$, $\dots$, $V\_{M-1}$.

Jimin made a cute weighted undirected graph $G$, which is a complete graph with the weight of an edge connecting vertices $u$ and $v$ is $\left\lvert A\_{u, (v \\, \bmod \\, K)} - A\_{v, (u \\, \bmod \\, K)} \right\rvert$. Eunsoo then found the minimum spanning tree of $G$.

However, Jongyoung brutally deleted edges of $G$ connecting $U\_i$ and $V\_i$ for $0 \le i \le M-1$. Note that $G$ may not be connected after deleting the edges.

Now, to help poor Jimin and Eunsoo, you should find the minimum spanning forest of $G$. A minimum spanning forest is a union of the minimum spanning trees of its connected components.

The first line contains three space-separated integers, $N$, $K$, and $M$.

Each of the following $N$ lines contains $K$ space-separated integers, $A\_{i,0},$ $\dots,$ $A\_{i,K-1}$. $(0 \le i \le N-1)$

Each of the following $M$ lines contains two space-separated integers, $U\_i$ and $V\_i$. $(0 \le i \le M-1)$

Output the sum of the weight of edges in the minimum spanning forest of $G$.

• $1 \le NK \le 300\\,000$
• $1 \le K \le N$
• $0 \le M \le \min\left(\frac{N(N-1)}{2},\ 300\\,000\right)$
• $-10^9 \le A\_{i,j} \le 10^9$ $(0 \le i \le N-1, 0 \le j \le K-1)$
• $0 \le U\_i < V\_i \le N - 1$ $(0 \le i \le M-1)$
• $(U\_i,$ $V\_i) \neq (U\_j,$ $V\_j)$ $(0 \le i < j \le M-1)$