시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB666100.000%

문제

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

Consider the following graph. Each cell of the grid is considered as a vertex. Two cells are connected by an edge if they are in the same row or column and the cost of the edge is equal to absolute difference of numbers in its endpoints.

Consider the minimal cost spanning tree of this graph (the cost of the spanning tree is the sum of costs of edges in it). Find its cost.

입력

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

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

출력

Print a single integer --- the cost of the minimal cost spanning tree.

예제 입력 1

2 3
0 2 4
3 4 5

예제 출력 1

7

예제 입력 2

3 4
1 7 10 2
5 6 8 3
0 5 2 7

예제 출력 2

16