Sakurako et son voyage#407

Sakurako et son voyage

1 seconde
256 mégaoctets
Hard

Cet été, Sakurako a décidé de visiter un nouveau pays. Après son arrivée, son guide touristique l'a mise en garde contre pièges à touristes qui pourraient lui faire dépenser de l'argent. La ville dans laquelle se trouve Sakurako peut être représentée comme une grille carrée de taille n\times n.

Actuellement, elle est en position . Sa tâche est d'arriver à l'aéroport qui est situé dans la case . Pendant son voyage, elle souhaite être le plus loin possible de tous les pièges à touristes.

Chaque piège à touristes a sa position (x_i, y_i). La distance entre la position actuelle de Sakurako (x_S, y_S) et le piège à touristes est calculée comme D(i, x_S, y_S)=|x_i-x_S|+|y_i-y_S|.

Au cours de son voyage à travers la grille, elle peut se déplacer vers n'importe quelle cellule adjacente ((x, y)\to (x+1,y);(x-1,y);(x,y-1);(x,y+1)) avec la contrainte que la nouvelle position soit une cellule valide dans la grille (1\le x_{new},y_{new}\le n).

Soit l'ensemble désignant toutes les cellules dans une grille que Sakurako visite pendant son voyage.

Votre tâche est de maximiser \displaystyle\min\limits_{\underset{(x,y)\in S}{i\in[1,m]}}D(i,x,y).

En d'autres termes, vous devez choisir le voyage de Sakurako de manière à maximiser la distance minimale à tous les pièges à touristes pendant son trajet. Vous devez afficher la distance minimale maximale possible.

Input

La première ligne contient deux entiers (2\le n \le 10^9; 1\le m\le 5\,000) — la taille de la grille et le nombre de pièges à touristes dans la ville.

Chacune des lignes suivantes contient deux entiers : x_i,y_i (1\le x_i, y_i\le n; (x_i,y_i)\neq(1,1); (x_i,y_i)\neq(n,n)), qui correspondent à la position du piège à touristes .

Output

Vous devez afficher un seul entier — la réponse à la tâche.

Examples

Example 1

Loading
Loading

Note

Un des chemins optimaux pour le premier exemple.

Scoring

  • ( points): n,m\le 100;

  • ( points): n,m\le 10^3;

  • ( points): n \le 10^3;

  • ( points): soit x_1=x_2=\dots=x_m ou y_1=y_2=\dots=y_m;

  • ( points): sans contraintes supplémentaires.