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