Problem G. Spin A Web

We have a canvas divided into grid with H rows and W columns. The square at the $i_th$ row from the top and the $j_th$ column from the left is represented as (i, j). (i, j) square has two value xi,j and yi,j .
Now we want to merge the squares to a connected web with minimal cost. Two squares can be connected if they are in the same row or column, and the cost of connecting ($i_0$, $j_0$) and ($i_1$, $j_1$) is|$x_{i_0,j_0}$ - $x_{i_1,j_1}$| + |$y_{i_0,j_0}$ - $y_{i_1,j_1}$|

Input is given from Standard Input in the following format:
H W
$x_{1,1}$ $x_{1,2}$ ... $x_{1,W}$
...
...
...
$x_{H,1}$ $x_{H,2}$ ... $x_{H,W}$
$y_{1,1}$ $y_{1,2}$ ... $y_{1,W}$
...
...
...
$y_{H,1}$ $y_{H,2}$ ... $y_{H,W}$
Constraints
1 ≤ H × W ≤ 100000
− 108 ≤ $x_{i,j}$ , $y_{i,j}$ ≤ 10^8(1 ≤ i ≤ H, 1 ≤ j ≤ W)
All of them are integers.

Print one line denotes the minimal cost to merge the square to be a connected web

1 3
1 3 2
1 2 3
2 2
1 4
2 3
2 1
3 4

5
8

2018 东北地区大学生程序设计竞赛