25121번 - 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)$

This subtask has an additional constraint: 

• $N \le 1\,000$

This subtask has additional constraints:

• $NK \le 150\,000$
• $M = 0$

This subtask has additional constraints:

• $NK \le 150\,000$
• $M \le 150\,000$

This subtask has no additional constraints.