Intervention des pompiers - II

Suite aux résultats peu rassurants de l'étude que vous venez de faire sur la proximité des casernes de pompiers au sein de votre ville, les pouvoirs publics envisagent la création d'une caserne supplémentaire.

Vous êtes chargé de déterminer jusqu'à combien on peut réduire la distance maximale d'une intersection à sa caserne la plus proche, telle que définie dans le problème précédent. Pour ce faire, vous pouvez ajouter une caserne à l'intersection la plus appropriée de la ville, sans déplacer les autres.

Ainsi, dans l'exemple ci-contre, où les casernes initiales sont représentées par des points rouges, ajouter la nouvelle caserne au point noir permet d'obtenir une distance maximale de 3, entre chaque intersection et la caserne qui en est la plus proche. En bleu, on a représenté un exemple d'intersection se trouvant à une telle distance après l'ajout de la caserne.

• 1 <= K <= 1 000, où K est le nombre de rues verticales et aussi le nombre de rues horizontales.
• 1 <= N <= 100 000, où N est le nombre de casernes de pompiers déjà présentes.
• 0 <= X,Y < K, où X et Y sont les coordonnées d'une intersection.

De plus, dans 50% des tests, on a K <= 100.

• La première ligne de l'entrée contient deux entiers séparés par un espace K et N.
• Chacune des N lignes suivantes contient deux entiers séparés par un espace : X_i et Y_i décrivant les coordonnées de la i-ème caserne de pompiers.

Vous devez écrire un seul entier sur la sortie : la distance maximale d'une intersection à la caserne la plus proche, une fois la caserne supplémentaire placée à la meilleure position possible.