金剛石 - 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