ダイヤモンド - Problem

地質調査によって、地下深くに埋まっているダイヤモンドの情報を表す地図が、下図のように作られた。

図の太い点はダイヤモンドの位置を表す。これから地面を掘ってダイヤモンドを採掘したい。

掘削する領域は、常に 2 本の対角線が座標軸に平行な正方形である。

以下、この正方形を D 正方形と呼ぶ。

現在の予算と掘削技術では、対角線の長さが $K$ の D 正方形の領域を 1 回だけ掘ることができる。

そこで、掘削する D 正方形の領域にできるだけ多くのダイヤモンドを含めたい。

地図の左下の点を座標の原点 $(0,0)$ とする。

各ダイヤモンドは整数座標上にある。

D 正方形の各頂点は整数座標を持たなければならず、

その中心、すなわち 2 本の対角線の交点は、必ず地図上（境界を含む）に位置しなければならない。

D 正方形の辺上にあるダイヤモンドも、その正方形に含まれるものとする。

例えば、下図で $K=4$ の場合、左の D 正方形は 5 個、右の D 正方形は 3 個のダイヤモンドを含む。

地質調査地図の情報を入力として、最も多くのダイヤモンドを含む D 正方形を求めるプログラムを作成せよ。

最初の行に 4 個の整数 $N$、$M$、$T$、$K$ が空白区切りで与えられる。

$N$ は地図の幅、$M$ は高さを表す（$1\le N,M\le1{,}000{,}000$）。

$T$ はダイヤモンドの数、$K$ は D 正方形の大きさ（対角線の長さ）を表す。

$T$ は $1$ 以上 $100$ 以下の整数、$K$ は $2$ 以上 $10{,}000{,}000$ 以下の偶数である。

2 行目からの $T$ 行には、それぞれ 2 個の整数 $A$ と $B$ が空白区切りで与えられる。

ここで、$(A,B)$ はダイヤモンドの位置の座標である（$0\le A\le N$、$0\le B\le M$）。

入力に与えられるダイヤモンドの座標はすべて異なる。

最初の行に、D 正方形の中心の座標 $(X,Y)$ を表す 2 個の整数 $X$ と $Y$ を空白区切りで出力せよ。

2 行目に、その D 正方形に含まれるダイヤモンドの数を出力せよ。

解が複数ある場合は、そのうちどれを出力してもよい。

5 4
5

QOJ.ac