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

서브태스크 1 (7점)

This subtask has an additional constraint:

• $N \le 1,000円$

서브태스크 2 (23점)

This subtask has additional constraints:

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

서브태스크 3 (46점)

This subtask has additional constraints:

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

서브태스크 4 (24점)

This subtask has no additional constraints.

힌트