Intervention des pompiers - I

Dans la lutte contre les incendies, ce qui est critique c'est le temps d'intervention. Vous connaissez peut-être déjà la règle : "lorsqu'un feu se déclenche, au bout d'une minute, cela nécessite un verre d'eau, au bout de deux minutes, un seau d'eau, et après trois minutes il faut une tonne d'eau". On souhaite donc s'assurer qu'il y a une caserne de pompiers à proximité de chaque habitation - car malheureusement les incendies ne sont pas toujours détectés dans les deux premières minutes ! Étant données la carte d'une ville et la position de ses casernes de pompiers, on va donc chercher l'endroit qui est le plus éloigné d'une caserne.

La carte de cette ville moderne est très simple : il s'agit d'une grille, avec K rues verticales et K rues horizontales. Les casernes de pompiers se trouvent toujours au niveau de l'intersection de deux rues. Votre but est de trouver, parmi toutes les intersections de rues se trouvant sur la carte, celle qui est la plus loin d'une caserne de pompiers. Vous devez alors afficher la distance entre cette intersection et la caserne qui en est la plus proche. L'illustration montre la carte de la ville. Les ronds rouges montrent les positions des casernes, le rond bleu indique le point le plus loin d'une caserne. Le résultat pour cette entrée est 4, et le chemin bleu indique une des manières d'atteindre cette distance.

• 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.
• 0 <= X,Y < K, où X et Y sont les coordonnées d'une intersection.

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

• 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.