#P1648. 看守

看守

题目描述

给出 dd 维空间的 nn 个点,求曼哈顿距离最大的两个点的曼哈顿距离。

两个 dd 维的点 (x1,x2,,xd)(x_1,x_2,\ldots,x_d)(y1,y2,,yd)(y_1,y_2,\ldots,y_d) 的曼哈顿距离定义为 x1y1+x2y2++xdyd|x_1-y_1|+|x_2-y_2|+\ldots+|x_d-y_d|

输入格式

第一行两个整数 nndd

接下来 nn 行,每行 dd 个整数描述一个点的坐标。

输出格式

输出最大的曼哈顿距离。

4 2
2 1
1 4
4 5
5 3
6

提示

数据规模与约定

  • 对于 60%60\% 的数据,保证 d2d\le2
  • 对于 100%100\% 的数据,保证 2n1062\le n\le10^6d4d\le4