金刚石 - Problem

地质勘探得到了一张表示深埋地下的金刚石信息的地图，如下图所示。

图中的粗点表示金刚石的位置。现在准备挖掘土地，开采金刚石。

挖掘区域始终是一个两条对角线分别平行于坐标轴的正方形。

以下将这样的正方形称为 D 正方形。

凭借现有的预算和挖掘技术，只能挖掘一次对角线长度为 $K$ 的 D 正方形区域。

因此，希望所挖掘的 D 正方形区域内包含尽可能多的金刚石。

将地图左下角的点作为坐标原点 $(0,0)$。

每颗金刚石均位于整数坐标处。

D 正方形的每个顶点都必须具有整数坐标，

并且其中心，即两条对角线的交点，必须位于地图上（包括边界）。

位于 D 正方形边上的金刚石也视为包含在该正方形内。

例如，下图中当 $K=4$ 时，左侧 D 正方形包含 5 颗金刚石，右侧 D 正方形包含 3 颗金刚石。

请编写程序，读取地质勘探地图的信息，求出包含金刚石最多的 D 正方形。

第一行给出四个整数 $N$、$M$、$T$、$K$，以空格分隔。

$N$ 表示地图的宽度，$M$ 表示地图的高度（$1\le N,M\le1{,}000{,}000$）。

$T$ 表示金刚石的数量，$K$ 表示 D 正方形的大小（对角线长度）。

$T$ 是 $1$ 至 $100$ 之间的整数，$K$ 是 $2$ 至 $10{,}000{,}000$ 之间的偶数。

从第二行起的 $T$ 行，每行给出两个整数 $A$ 和 $B$，以空格分隔。

其中，$(A,B)$ 为一颗金刚石的位置坐标（$0\le A\le N$，$0\le B\le M$）。

输入给出的所有金刚石坐标互不相同。

第一行输出两个整数 $X$、$Y$，以空格分隔，表示 D 正方形中心的坐标 $(X,Y)$。

第二行输出该 D 正方形中包含的金刚石数量。

如果有多个答案，输出其中任意一个。

5 4
5

QOJ.ac