Énoncé du problème

À la fin de l'année dernière, le Père Noël a oublié de distribuer les cadeaux de Noël aux enfants du village JOI. Pour s'excuser, il a donc décidé d'apporter des gâteaux au chocolat aux enfants. Comme le jour de la livraison est demain, il est grand temps de réfléchir à un plan de déplacement.

Le village JOI est découpé en damier par $W$ routes rectilignes s'étendant du nord au sud et $H$ routes rectilignes s'étendant d'est en ouest. Les $W$ routes nord-sud sont numérotées $1, 2, \dots, W$ dans l'ordre en partant de l'ouest, et les $H$ routes est-ouest sont numérotées $1, 2, \dots, H$ dans l'ordre en partant du sud. L'intersection où se croisent la $x$-e route nord-sud depuis l'ouest et la $y$-e route est-ouest depuis le sud est notée $(x, y)$. Il y a $N$ maisons dans le village JOI, et chacune d'elles est située à l'une des intersections. Le Père Noël ne peut se déplacer que le long des routes. Le temps nécessaire pour se déplacer entre deux intersections adjacentes est égal à $1$.

Comme il y a des enfants dans toutes les maisons du village JOI, le Père Noël doit passer par toutes les maisons du village JOI pour livrer $1$ gâteau au chocolat à chacune. Comme il est un peu dangereux de voler dans les airs avec ses rennes tout en transportant de précieux gâteaux au chocolat, le Père Noël et ses rennes ont décidé d'atterrir à l'une des intersections du village JOI, d'où le Père Noël partira à pied pour livrer les gâteaux au chocolat. Le Père Noël ne marche jamais en portant $2$ gâteaux au chocolat ou plus en même temps. Autrement dit, chaque fois que le Père Noël livre un gâteau au chocolat à $1$ maison, il revient à l'intersection où il a atterri.

Le Père Noël a décidé de choisir un plan de déplacement qui minimise le temps total nécessaire depuis son atterrissage dans le village JOI jusqu'à ce qu'il ait livré les gâteaux au chocolat à toutes les maisons. Attention : le temps nécessaire pour revenir à l'intersection d'atterrissage après avoir livré le gâteau au chocolat à la dernière maison n'est pas compté dans le temps requis. De plus, rien d'autre que le temps de déplacement n'est pris en compte.

Étant donné les informations sur l'emplacement des maisons, écrivez un programme permettant de trouver la valeur minimale du temps requis depuis l'atterrissage dans le village JOI jusqu'à la livraison des gâteaux au chocolat à toutes les maisons lorsque le Père Noël choisit judicieusement l'intersection d'atterrissage, ainsi que l'emplacement de l'intersection où il doit atterrir pour minimiser ce temps requis.

Entrée

Lisez l'entrée suivante depuis l'entrée standard :

• La $1$-re ligne contient les entiers $W, H$ séparés par un espace, représentant le nombre de routes dans chaque direction.
• La $2$-e ligne contient un entier $N$, représentant le nombre de maisons.
• Les $N$ lignes suivantes contiennent les informations sur l'emplacement des maisons. La $(i + 2)$-e ligne ($1 \le i \le N$) contient les entiers $X_i, Y_i$ séparés par un espace, indiquant que la $i$-e maison est située à l'intersection $(X_i, Y_i)$. Ces $N$ intersections sont toutes distinctes.

Sortie

Affichez les données suivantes sur la sortie standard :

• La $1$-re ligne doit contenir $1$ entier représentant la valeur minimale du temps requis.
• La $2$-e ligne doit contenir les $2$ entiers $x, y$ séparés par un espace dans cet ordre, lorsque l'intersection où le Père Noël doit atterrir pour minimiser le temps requis est $(x, y)$. S'il existe plusieurs intersections appropriées, choisissez parmi elles celle qui est la plus à l'ouest (c'est-à-dire celle dont la valeur de $x$ est minimale) ; si cela ne suffit toujours pas à en déterminer $1$ seule, choisissez parmi celles-ci celle qui est la plus au sud (c'est-à-dire celle dont la valeur de $y$ est minimale).

Exemple

Exemple 1

Entrée

5 4
3
1 1
3 4
5 3

Sortie

10
3 3

Explication

Par exemple, le temps requis peut être minimisé grâce au plan de déplacement suivant :

• Atterrir à l'intersection $(3, 3)$.
• Livrer un gâteau au chocolat à la maison située à l'intersection $(3, 4)$. Le temps écoulé jusqu'ici est $1$.
• Revenir à l'intersection $(3, 3)$. Le temps écoulé jusqu'ici est $2$.
• Livrer un gâteau au chocolat à la maison située à l'intersection $(5, 3)$. Le temps écoulé jusqu'ici est $4$.
• Revenir à l'intersection $(3, 3)$. Le temps écoulé jusqu'ici est $6$.
• Livrer un gâteau au chocolat à la maison située à l'intersection $(1, 1)$. Le temps écoulé jusqu'ici est $10$.

Exemple 2

Entrée

4 6
8
1 3
3 2
4 4
2 5
2 3
3 3
3 4
2 4

Sortie

21
2 3

Explication

Notez qu'il est permis d'atterrir à une intersection où se trouve une maison.

Contraintes

• $1 \le W \le 1000000000 = 10^9$ : le nombre de routes s'étendant du nord au sud.
• $1 \le H \le 1000000000 = 10^9$ : le nombre de routes s'étendant d'est en ouest.
• $1 \le N \le 100000 = 10^5$ : le nombre de maisons.
• $1 \le X_i \le W$ : le numéro de la route nord-sud pour l'emplacement de la $i$-e maison.
• $1 \le Y_i \le H$ : le numéro de la route est-ouest pour l'emplacement de la $i$-e maison.

Notez que dans ce problème, la plage des entiers manipulés peut dépasser $32$ bits.

Barème

• Pour des jeux de tests valant $40\%$ du score total, $N \le 1000$ est vérifiée.
• Pour des jeux de tests valant $10\%$ du score total, $W \le 50, H \le 50, N \le 1000$ sont vérifiées.