Une étude géologique a produit une carte des diamants enfouis profondément sous terre, comme illustré ci-dessous.
Les gros points de la figure indiquent les positions des diamants. Nous souhaitons maintenant creuser le sol pour les extraire.
La région excavée doit toujours être un carré dont les deux diagonales sont parallèles aux axes de coordonnées.
Nous appellerons désormais ce carré un carré D.
Le budget et les techniques disponibles ne permettent de creuser qu’une seule fois une région carrée D de diagonale de longueur $K$.
Nous souhaitons donc que la région carrée D choisie contienne le plus grand nombre possible de diamants.
Le coin inférieur gauche de la carte est l’origine $(0,0)$.
Chaque diamant se trouve à des coordonnées entières.
Chaque sommet du carré D doit avoir des coordonnées entières,
et son centre, c’est-à-dire l’intersection des deux diagonales, doit se trouver sur la carte, bord compris.
Un diamant situé sur un côté du carré D est également considéré comme contenu dans celui-ci.
Par exemple, dans la figure ci-dessous, pour $K=4$, le carré D de gauche contient 5 diamants et celui de droite en contient 3.
Écrivez un programme qui, à partir de la carte géologique, trouve un carré D contenant le plus grand nombre de diamants.
Entrée
La première ligne contient quatre entiers $N$, $M$, $T$ et $K$, séparés par des espaces.
$N$ est la largeur de la carte et $M$ sa hauteur ($1\le N,M\le1{,}000{,}000$).
$T$ est le nombre de diamants et $K$ la taille du carré D (la longueur de sa diagonale).
$T$ est un entier de $1$ à $100$, et $K$ est un entier pair de $2$ à $10{,}000{,}000$.
Chacune des $T$ lignes suivantes contient deux entiers $A$ et $B$, séparés par une espace.
Le couple $(A,B)$ indique la position d’un diamant ($0\le A\le N$, $0\le B\le M$).
Toutes les coordonnées des diamants fournies sont distinctes.
Sortie
Sur la première ligne, affichez deux entiers $X$ et $Y$, séparés par une espace, représentant le centre $(X,Y)$ du carré D.
Sur la deuxième ligne, affichez le nombre de diamants contenus dans ce carré D.
S’il existe plusieurs réponses, affichez n’importe laquelle.
Exemples
Entrée 1
10 8 9 4 2 2 3 4 9 3 9 5 8 2 4 5 4 3 5 3 6 4
Sortie 1
5 4 5