Belle étoile

Pour vous, les étoiles ne forment pas de magnifiques créatures ou personnages, ni même la moindre casserole. Vous avez toujours trouvé cela absurde d'apprendre par coeur les noms et positions des diverses constellations. Après tout, en cherchant bien, il est possible de trouver n'importe-quelle forme en reliant des groupes d'étoiles, tout est une question d'imagination. Vous décidez donc de rechercher vos propres formes dans le ciel.

Pour pimenter un peu les choses, vous proposez un petit concours à vos amis : le but est de trouver la plus grande flèche possible dans le ciel étoilé. Tous les moyens sont permis dans ce concours et alors que vos amis regardent tous au dessus d'eux, vous sortez discrètement votre appareil photo numérique et votre ordinateur portable, afin de vous assurer la victoire.

Vous devez écrire un programme qui trouve la plus grande flèche composée de trois étoiles exactement. Votre flèche doit être dirigée vers le haut, et les deux étoiles du côté gauche et droit de la flèche doivent se trouver exactement à la même hauteur. L'étoile qui forme la pointe de la flèche doit avoir son abscisse située strictement entre celle des deux autres et son ordonnée doit être strictement au dessus des deux autres.

Pour finir, la largeur de la flèche doit être plus petite ou égale à sa hauteur. Notez que la largeur de la flèche est définie comme étant la différence entre l'abscisse de l'étoile la plus à gauche et celle de l'étoile la plus à droite. La hauteur de la flèche est définie comme étant la différence entre l'ordonnée de la pointe de la flèche et celle des deux étoiles en dessous.

Ainsi, si les trois étoiles qui forment la flèche sont aux coordonnées (X₁,Y₁), (X₂,Y₂) et X₃,Y₃), on doit avoir X₁ < X₂ < X₃ et Y₂ < Y₁ = Y₃. La largeur de la flèche est X₃-X₁ et la hauteur de la flèche est Y₁-Y₂ et on doit donc avoir X₃-X₁ <= Y₁-Y₂. Le diagramme suivant illustre quelques flèches valides et invalides.

Flèches valides	Flèches invalides

La taille d'une flèche est définie comme étant sa largeur plus sa hauteur. Lorsque vous cherchez la flèche la plus grande, vous recherchez donc la flèche dont la hauteur plus la largeur est la plus grande possible.

• 3 <= N <= 2000, où N est le nombre d'etoiles visibles dans le ciel.
• 0 <= X, Y <= 1,000,000
, où X, Y sont les coordonnées d'une étoile.

Chacune des N lignes suivantes décrit une étoile et contient deux entiers positifs séparés par un espace : les coordonnées X et Y de l'étoile. On vous garantit qu'il n'y a pas deux étoiles à la même position dans le ciel.

On vous garantit qu'il existe toujours au moins une flèche valide.

L'exemple d'entrée représente le ciel étoilé illustré ci-dessus et la flèche la plus grande est indiquée sur le diagramme. Les trois étoiles formant cette flèche sont aux coordonnées (7,19), (8,1) et (14,19). Cette flèche a pour largeur 14-7=7 et pour hauteur 19-1=18, ce qui donne une taille totale de 7+18=25.