Minimum Spanning Tree of a Grid Graph

Time limit2sMemory limit512 MB

Summary

Given an n by m grid of integers, build a graph connecting any two cells in the same row or column with edge weight equal to their absolute difference, and output the MST cost.

Level: Hard8 of 10
Topics: Minimum spanning tree, Greedy, Sorting, Union-find
Solved: No attempts yet

Problem

You are given an $n \times m$ grid of integers.

Consider the following graph. Each cell of the grid is a vertex. Two cells are connected by an edge if they lie in the same row or the same column, and the cost of that edge equals the absolute difference of the numbers at its endpoints.

Find the cost of the minimum spanning tree of this graph, where the cost of a spanning tree is the sum of the costs of its edges.

Input

The first line contains two integers $n$ and $m$ , the number of rows and columns of the grid. ( $1 \leq n \cdot m \leq 10^5$ )

$n$ lines follow. The $i$ -th of them contains $m$ integers $a_{i,j}$ , the elements of the grid. ( $0 \leq a_{i,j} < 10^9$ )

Output

Print a single integer, the cost of the minimum spanning tree.

Examples2

Example 1
Input
```
2 3
0 2 4
3 4 5
```
Expected output
```
7
```
Example 2
Input
```
3 4
1 7 10 2
5 6 8 3
0 5 2 7
```
Expected output
```
16
```