이상한 그래프

$N \times K$ 크기의 정수 2차원 배열 $A$가 주어진다. 원소는 $A_{0,0}, A_{0,1}, \dots, A_{0,K-1}, A_{1,0}, \dots, A_{N-1,K-1}$이다. 또 크기가 $M$인 정수 배열 $U = U_0, \dots, U_{M-1}$과 $V = V_0, \dots, V_{M-1}$이 주어진다.

지민이 가중치가 있는 무방향 완전 그래프 $G$를 만들었다. 정점 $u$와 $v$를 잇는 간선의 가중치는 $\left\lvert A_{u, (v \bmod K)} - A_{v, (u \bmod K)} \right\rvert$이다. 은수가 $G$의 최소 스패닝 트리를 구했다.

이후 종영이 $0 \le i \le M-1$인 모든 $i$에 대해 $U_i$와 $V_i$를 잇는 간선을 삭제했다. 간선을 삭제하면 $G$가 연결되지 않을 수 있다.

간선을 삭제하고 남은 그래프의 최소 스패닝 포레스트를 구하라.

첫 줄에 정수 $N$, $K$, $M$이 공백으로 구분되어 주어진다.

다음 $N$개 줄에는 각각 $K$개의 정수 $A_{i,0}, \dots, A_{i,K-1}$이 주어진다. ($0 \le i \le N-1$)

다음 $M$개 줄에는 두 정수 $U_i$와 $V_i$가 주어진다. ($0 \le i \le M-1$)

최소 스패닝 포레스트에 포함된 간선 가중치의 합을 출력한다.

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