Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

You are given $N$ points in $D$-dimensional space. The $i^{th}$ point has $D$ coordinates - $x_{i, 1}, x_{i, 2}, \ldots, x_{i, D}$.

Consider a weighted undirected complete graph with these $N$ points as its vertices. Weight of the edge between points $i$ and $j$ is $|x_{i,1} - x_{j, 1}| + |x_{i,2} - x_{j, 2}| + \ldots + |x_{i, D} - x_{j,D}|$.

Find the weight of the [maximum spanning tree] of this graph.

------ Input: ------

The first line contains two integers $N, D$.
The $i$-th of the next $N$ lines contains a description of the $i$-th point. It has $D$ integers: $x_{i, 1}, x_{i, 2}, \ldots, x_{i,D}$.

------ Output: ------
Output a single line which contains a single integer - the Maximum Spanning Tree Weight

------ Constraints ------
$1 ≤ D ≤ 5$
$1 ≤ N ≤ 200\,000$
$0 ≤ x_{i, j} ≤ 100\,000$

------ Subtasks ------
10 points, $N ≤ 5000$

90 points, $N ≤ 200\,000$

----- Sample Input 1 ------
2 2

1 1

2 2
----- Sample Output 1 ------
2

见题面

见题面