题目描述

Vojtěch Jarník（1897—1970）被认为是最有影响力的捷克数学家之一。他在数学分析和数论方面作出了重要贡献，也因最小生成树算法而广为人知。

鲜为人知的是，他和另一位伟大的捷克数学家 Otakar Borůvka 都对鸟类学感兴趣，尤其关注高维空间中的鸟类。

高维乌鸦喜欢在某一个维度上排成一条直线，并且希望保持彼此之间原有的距离。

一只乌鸦的位置由一个包含 $D$ 个整数坐标的向量表示。一步操作可以选择一只乌鸦，并将它的某一个坐标增加 $1$ 或减少 $1$。允许多只乌鸦位于完全相同的位置。

请计算最少需要多少步，才能使所有乌鸦到达满足下列条件的配置：

1. 存在某一个坐标维度，使所有乌鸦在其余 $D-1$ 个维度上的坐标都分别相同；换言之，所有乌鸦位于一条平行于某条坐标轴的直线上。
2. 任意两只乌鸦之间的曼哈顿距离与移动前完全相同。

两个向量

$$a=(a_1,a_2,\ldots,a_D),\qquad b=(b_1,b_2,\ldots,b_D)$$

之间的曼哈顿距离定义为

$$\operatorname{dist}(a,b)=\sum_{i=1}^{D}|a_i-b_i|.$$

输入格式

第一行包含两个整数 $N,D$（$1\le N\cdot D\le 10^5$），分别表示乌鸦数量和维度数。

接下来 $N$ 行，每行包含 $D$ 个整数，表示一只乌鸦的坐标。每个坐标均位于 $[-10^9,10^9]$ 范围内。

输出格式

输出一个整数，表示达到目标配置所需的最少步数。

若不存在满足要求的配置，输出 -1。

样例 1

输入

5 2
0 0
1 1
3 3
4 4
2 2

输出

12

样例 2

输入

3 3
10 5 6
20 3 4
30 1 2

输出

16